Assigning labels in an unknown anonymous network with a leader

We consider the task of assigning distinct labels to nodes of an unknown an onymous network in a distributed manner. A priori, nodes do not have any id entities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algori thms, 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 th e algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of round s required for the label assignment, and the message and bit complexities o f the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms w hose time and message complexity are asymptotically optimal and which assig n short labels. On the other hand, we establish inherent tradeoffs between quality and efficiency for labeling algorithms.