טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYifrach Ayelet
SubjectImproved Distributed Exploration of Anonymous Networks
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Shay Kutten
Full Thesis textFull thesis text - English Version


Abstract

This thesis considers an anonymous and asynchronous network in which the nodes do not have identities nor do they hold maps of the network. A group of k identical agents, with no knowledge of the network’s topology nor of one another, starts exploring the network (encompassing n nodes) by executing identical algorithms. An agent visiting any node can write to and read from the whiteboard of that node. The agents’ goal is to construct a labeled map of the network, the same map for all the agents. We improve on the previous algorithm of Das, Flocchini, Nayak and Santoro that constructs a map of the network provided that n and k are co-prime. Their algorithm uses O(mk) edge traversals where m is the number of edges in the network. By introducing the requirement that an agent has the knowledge of either n or k and also that n is co-prime to k we ensure that our algorithm will always terminate successfully and construct such a map using no more than O(m∙logk) edge traversals. The size of the whiteboard memory needed in our algorithm is O(logn) - the same as in the algorithm of Das et al. The new algorithm uses techniques taken from leader election. However, these techniques had to be modified to deal with the fact that leadership candidates that are "near by" to each other (in terms of network distance) may "look" identical to each other. Hence, the traditional methods of electing first "local leaders" among adjacent candidates for leadership may deadlock if we are not careful. Finally, we generalize the results to other cases where the problem is solvable.