An asynchronous leader election algorithm for dynamic networks

摘要

An algorithm for electing a leader in an asynchronous network with dynamically changing communication topology is presented. The algorithm ensures that, no matter what pattern of topology changes occur, if topology changes cease, then eventually every connected component contains a unique leader. The algorithm combines ideas from the temporally ordered routing algorithm (TORA) for mobile ad hoc networks (Park and Corson, 1997) with a wave algorithm (Tel, 2000), all within the framework of a height-based mechanism for reversing the logical direction of communication links (Gafni and Bertsekas, 1981). It is proved that in certain well-behaved situations, a new leader is not elected unnecessarily.