Assigning labels in unknown anonymous networks
P. Fraigniaud, A. Pelc, D. Peleg, S. Perennes
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
We consider the task of distributedly assigning distinct labels 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
(unknown network). They execute identical algorithms, apart from a distinguished
node, called the source, which 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.