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 synchronization. Determining the weakest assumptions, under which leader election is possible, remains an unresolved problem. In this study we present a leader election algorithm that operates in the presence of changes and under weak (realistic) assumptions regarding message delays and regarding the clock drifts of the distributed nodes. The proposed algorithm is self-sufficient, easy to implement and can be extended to support multiple regions, self-stabilization, and wireless ad-hoc networks. We prove the algorithm's correctness and provide a complexity analysis of the time, space, and number of messages required to elect a leader.
Numerous algorithms exist in the literature for distributed leader election in static, as well as dynamic networks, with different settings @cite_25 . We begin with a description of the most relevant characteristics of existing leader election algorithms:
@cite_25
1526359699
1. Introduction.PART I: FUNDAMENTALS.2. Basic Algorithms in Message-Passing Systems.3. Leader Election in Rings.4. Mutual Exclusion in Shared Memory.5. Fault-Tolerant Consensus.6. Causality and Time.PART II: SIMULATIONS.7. A Formal Model for Simulations.8. Broadcast and Multicast.9. Distributed Shared Memory.10. Fault-Tolerant Simulations of Read Write Objects.11. Simulating Synchrony.12. Improving the Fault Tolerance of Algorithms.13. Fault-Tolerant Clock Synchronization.PART III: ADVANCED TOPICS.14. Randomization.15. Wait-Free Simulations of Arbitrary Objects.16. Problems Solvable in Asynchronous Systems.17. Solving Consensus in Eventually Stable Systems.References.Index.