Pale: Time bounded practical agile leader election

Bronislav Sidik, Rami Puzis, Polina Zilberman, Yuval Elovici

IEEE Transactions on Parallel and Distributed Systems 31 (2), 470-485, 2019

Many tasks executed in dynamic distributed systems, such as sensor networks or enterprise environments with bring-your-own-device policy, require central coordination by a leader node. In the past it has been proven that distributed leader election in dynamic environments with constant changes and asynchronous communication is not possible. Thus, state-of-the-art leader election algorithms are not applicable in asynchronous environments with constant network changes. Some algorithms converge only after the network stabilizes (an unrealistic requirement in many dynamic environments). Other algorithms reach consensus in the presence of network changes but require a global clock or some level of communication synchrony. Determining the weakest assumptions, under which bounded leader election is possible, remains an unresolved problem. In this study we present a leader election algorithm that …