M.Sc Student | Yifrach Ayelet |
---|---|

Subject | Improved Distributed Exploration of Anonymous Networks |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Shay Kutten |

Full Thesis text |

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(*m*∙*k*)
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*∙log*k*) edge traversals. The size of the
whiteboard memory needed in our algorithm is O(log*n*) - 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.