Improved Distributed Exploration of Anonymous Networks
Shantanu Das Shay Kutten and Ayelet Yifrach
Abstract:
The problem of constructing a labeled map of an anonymous and asynchronous network is
addressed. We present an algorithm that explores and maps the network by using k identical
agents that have no prior knowledge of the network topology. An algorithm of Das, Flocchini,
Nayak and Santoro for mapping of the network requires that n and k are co-prime. Our
improved algorithm, presented here, requires at most O(m·logk) edge traversals, while
theirs uses O(m·k) edge traversals (m is the number of edges in the network). The size of
the whiteboard memory needed in our algorithm is the same as that used in DFNS algorithm
O(logn). We employ techniques utilized in solutions to the Leader Election task, and
introduce a modification to resolve issues of electing first “local leaders” among adjacent
candidates, which otherwise may deadlock the process.
Keywords: anonymous network, unlabeled nodes, asynchronous distributed leader election, k
agents, map construction.