On bootstrapping topology knowledge in anonymous networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On bootstrapping topology knowledge in anonymous networks

Full text

Pdf (1.76 MB)

Source

ACM Transactions on Autonomous and Adaptive Systems (TAAS) archive
Volume 4 , Issue 1 (January 2009) table of contents

Article No. 8

Year of Publication: 2009

ISSN:1556-4665

Authors

Toshimitsu Masuzawa	Osaka University, Japan
Sébastien Tixeuil	Université Pierre et Marie Curie, Paris, France

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 110, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1462187.1462195 What is a DOI?

ABSTRACT

In this article, we quantify the amount of “practical” information (i.e., views obtained from the neighbors, colors attributed to the nodes and links) to obtain “theoretical” information (i.e., the local topology of the network up to distance k) in anonymous networks. In more detail, we show that a coloring at distance 2k + 1 is necessary and sufficient to obtain the local topology at distance k that includes outgoing links. This bound drops to 2k when outgoing links are not needed. A second contribution of this article deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that (i) with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and (ii) with a central daemon, it is impossible to achieve distance m when instantaneous topology knowledge is limited to m − 1. On the positive side, we show that (i) under the k-central daemon, deterministic self-stabilizing bootstrap of colors up to distance k is possible provided that k-local topology can be instantaneously obtained, and (ii) under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Beauquier, J., Delaët, S., Dolev, S., and Tixeuil, S. 2007. Transient fault detectors. Distrib. Comput. 20, 1, 39--51.
	2	Joffroy Beauquier , Maria Gradinariu , Colette Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.199-207, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301358]
	3	Paolo Boldi , Sebastiano Vigna, Universal dynamic synchronous self-stabilization, Distributed Computing, v.15 n.3, p.137-153, July 2002 [doi>10.1007/s004460100062]
	4	Danturi, P., Nesterenko, M., and Tixeuil, S. 2006. Self-stabilizing philosophers with generic conflicts. In proceedings of the 8th International Symposium on Stebilization, Safety, and Security on Distributed Systems (SSS'06), A. K. Datta and M. Gradinariu, Eds. Lecture Notes in Computer Science, vol. 4280. Springer-Verlag, 214--230.
	5	Sylvie Delaët , Sébastien Tixeuil, Tolerating transient and intermittent failures, Journal of Parallel and Distributed Computing, v.62 n.5, p.961-981, May 2002 [doi>10.1006/jpdc.2001.1827]
	6	Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
	7	Dolev, S., Gouda, M. G., and Schneider, M. 1999. Memory requirements for silent stabilization. Acta Inf. 36, 6, 447--462.
	8	Dolev, S. and Herman, T. 1997. Superstabilizing protocols for dynamic distributed systems. Chicago J. Theor. Comput. Sci.
	9	Pierre Fraigniaud , Andrzej Pelc , David Peleg , Stéphane Pérennes, Assigning labels in an unknown anonymous network with a leader, Distributed Computing, v.14 n.3, p.163-183, October, 2001 [doi>10.1007/PL00008935]
	10	Mohamed G. Gouda , Ted Herman, Adaptive Programming, IEEE Transactions on Software Engineering, v.17 n.9, p.911-921, September 1991 [doi>10.1109/32.92911]
	11	Gradinariu, M. and Tixeuil, S. 2000. Self-stabilizing vertex coloring of arbitrary graphs. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'00), 55--70.
	12	Herman, T. and Tixeuil, S. 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proceedings of the 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'04). Lecture Notes in Computer Science, vol. 3121, Springer-Verlag, 45--58.
	13	Jason L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
	14	Masuzawa, T. 1995. A fault-tolerant and self-stabilizing protocol for the topology problem. In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 1.1--1.15.
	15	Mitton, N., Fleury, E., Guérin-Lassous, I., Séricola, B., and Tixeuil, S. 2006. On fast randomized colorings in sensor networks. In Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS'06). IEEE Press, 31--38.
	16	N. Mitton , E. Fleury , I. Guerin Lassous , S. Tixeuil, Self-Stabilization in Self-Organized Multihop Wireless Networks, Proceedings of the Second International Workshop on Wireless Ad Hoc Networking, p.909-915, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.122]
	17	John T. Moy, OSPF: Anatomy of an Internet Routing Protocol, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	18	Perlman, R. 2000. Interconnexion Networks. Addison-Wesley.
	19	Sakamoto, N. 2000. Structure of initial conditions for distributed algorithms. IEICE Trans. Inform. Syst. E83-D, 12, 2029--2038.
	20	Spinelli, J. and Gallager, R. 1989. Event driven topology broadcast without sequence numbers. IEEE Trans. Comm. 37, 468--474.
	21	Masafumi Yamashita , Tsunehiko Kameda, Leader Election Problem on Networks in which Processor Identity Numbers Are Not Distinct, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.878-887, September 1999 [doi>10.1109/71.798313]