A DIRECTED-SPANNING-TREE BASED DISTRIBUTED ELECTION ALGORITHM

This paper proposes a distributed election algorithm in general network topology. It is assumed that there exists a directed spanning tree of the network topology. As a synchronizer, the directed spanning tree avoids unnecessary message transmission. For a distributed system composed of n processors, the message complexity of this algorithm is O（n）. The algorithm is optimal within a constant factor.