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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Gafni, E.: Time and Message bounds for Election in Synchronous and Asynchronous Complete Networks. SICOMP 20(2), 376–394 (1991)
Afek, Y., Matias, Y.: Elections in Anonymous Networks. Information and Computation 113(2), 312–330 (1994)
Albers, S., Henzinger, M.R.: Exploring Unknown Environments. SIAM Journal on Computing 29(4), 1164–1188 (2000)
Angluin, D.: Local and global properties in networks of processors. In: Proc. ACM STOC, pp. 82–93 (1980)
Awerbuch, B.: A new distributed depth-first-search algorithm. Information Processing Letters 20(3), 147–150 (1985)
Barriere, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Electing a leader among anonymous mobile agents in anonymous networks with sense-of-direction. Technical Report LRI-1310, Univ. Paris-Sud, France (2002)
Barriere, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Rendezvous and Election of Mobile Agents: Impact of Sense of Direction. Theory of Computing Systems (2005)
Bender, M.A., Slonim, D.K.: The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs. In: Proc. FOCS 1994, pp. 75–85 (1994)
Chlamtac, I., Kutten, S.: Tree-based broadcasting in multihop radio networks. IEEE Transactions on Computers 36(10), 1209–1223 (1987)
Cidon, I.: Yet another distributed depth-first-search algorithm. Information Processing Letters 26(6), 301–305 (1988)
Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-Guided Graph Exploration by a Finite Automaton. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 335–346. Springer, Heidelberg (2005)
Das, S., Flocchini, P., Nayak, A., Santoro, N.: Distributed Exploration of an Unknown Graph. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 99–114. Springer, Heidelberg (2005)
Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theoretical Computer Science 326, 343–362 (2004)
Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. Journal of Algorithms 51, 38–63 (2004)
Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. In: Proc. 6th Latin American Theoretical Informatics Symp., pp. 141–151 (2004)
Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., Tixeuil, S.: Space Lower Bounds for Graph Exploration via Reduced Automata. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 140–154. Springer, Heidelberg (2005)
Fraigniaud, P., Pelc, A., Peleg, D., Perennes, S.: Assigning labels in unknown anonymous networks. In: Proc. ACM PODC 2000, pp. 101–111 (2000)
Gallager, R.G., Humblet, P.M., Spira, P.M.: A Distributed Algorithm for Minimum-Weight Spanning Trees. ACM TOPLAS 5(1), 66–77 (1983)
Kameda, T., Yamashita, M.: Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases. IEEE TPDS 7(1), 69–89 (1996)
Korach, E., Kutten, S., Moran, S.: A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms. ACM TOPLAS 12(1), 84–101 (1990)
Kranakis, E., Santoro, N., Sawchuk, C., Krizanc, D.: Mobile Agent Rendezvous in a Ring. In: Proc. 23rd IEEE ICDCS 2003, p. 592 (2003)
LeLann, G.: Distributed Systems - Towards a Formal Approach. In: Proc. IFIP Congress, pp. 155–160 (1977)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. In: Proc. 9th ACM-SIAM symposium on Discrete algorithms, pp. 316–322 (1998)
Sakamoto, N.: Comparison of initial conditions for distributed algorithms on anonymous networks. In: Proc. ACM PODC 1999, pp. 173–179 (1999)
Sharir, M.: A strong-connectivity algorithm and its application in data flow analysis. Computers and Mathematics with Applications 7(1), 67–72 (1981)
Tarjan, R.E.: Depth first search and linear graph algorithms. SICOMP 1(2), 146–160 (1972)
Tel, G.: Introduction to Distributed Algorithms, pp. 198–213. Cambridge University Press, Cambridge (1994)
Villadangos, J., Cordoba, A., Farina, F., Prieto, M.: Efficient Leader Election in Complete Networks. In: Proc. 13th PDP 2005, pp. 138–143 (2005)
Yifrach, A.: Improved Distributed Exploration of Anonymous Networks. MSc Thesis, Faculty of Industrial Engineering and Management, Technion Israel Institute of Technology, Haifa, Israel (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, S., Kutten, S., Yifrach, A. (2006). Improved Distributed Exploration of Anonymous Networks. In: Chaudhuri, S., Das, S.R., Paul, H.S., Tirthapura, S. (eds) Distributed Computing and Networking. ICDCN 2006. Lecture Notes in Computer Science, vol 4308. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11947950_34
Download citation
DOI: https://doi.org/10.1007/11947950_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68139-7
Online ISBN: 978-3-540-68140-3
eBook Packages: Computer ScienceComputer Science (R0)