Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks

摘要

We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. From the complexity viewpoint, our algorithms offer a polynomial complexity (memory, number of messages and size of messages).