Assigning Labels in Unknown Anonymous Networks
Pierre Fraigniaud, Andrzej Pelc, David Peleg, Stéphane Pérennès · 2000
We consider the task of distributedly assigning distinct la-bels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (un-known network). They execute identical algorithms, apart from a distinguished node, called the source, which start-s 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 mes-sage 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 op-timal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.