Assigning labels in an unknown anonymous network with a leader |
| |
Authors: | Pierre Fraigniaud Andrzej Pelc David Peleg Stéphane Pérennes |
| |
Affiliation: | (1) Laboratoire de Recherche en Informatique -- CNRS, Université Paris-Sud, 91405 Orsay, France (e-mail: pierre@lri.fr) , FR;(2) Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, 76100 Israel (e-mail: peleg@wisdom.weizmann.ac.il) , IL;(3) Département d'Informatique, Université du Québec à Hull, Hull, Québec J8X 3X7, Canada (e-mail: pelc@uqah.uquebec.ca) , CA;(4) SLOOP I3S-CNRS/INRIA, Université de Nice-Sophia Antipolis, 2004 Route des Lucioles, BP 93, 06902 Sophia Antipolis Cedex, France (e-mail: Stephane.Perennes@sophia.inria.fr) , FR |
| |
Abstract: | We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms. Received: July 2000 / Accepted: February 2001 |
| |
Keywords: | : Distributed system – Anonymous network – Label assignment |
本文献已被 SpringerLink 等数据库收录! |
|