Comparative Analysis of Leader Election Algorithms In Distributed Systems
Keywords:
Leader election, distributed systems, consensus algorithm, Raft, Paxos, fault tolerance, ring networks, message complexityAbstract
Leader election is a fundamental problem in distributed computing, requiring processes to agree on a single coordinator to manage critical operations such as mutual exclusion, transaction coordination, and state machine replication. This paper presents a comprehensive comparative analysis of leader election algorithms across multiple dimensions: message complexity, time complexity, fault tolerance, and practical applicability. We examine classical ring-based algorithms (Chang-Roberts, Hirschberg-Sinclair), complete network algorithms (Bully), and modern consensus-based approaches (Paxos, Raft, ZAB). Through systematic evaluation using both theoretical analysis and empirical experimental simulation, we identify trade-offs between algorithm simplicity, efficiency, and robustness. Our results indicate that while ring-based algorithms offer optimal message complexity of O(N log N ), consensus-based algorithms such as Raft provide superior fault tolerance and practical implementation characteristics for modern distributed systems. We synthesize these findings into a decision framework for practitioners selecting leader election mechanisms based on system requirements and operational constraints.
References
[1] E. Chang and R. Roberts, “An improved algorithm for decentralized extrema-finding in circular configurations of processes,” Communications of the ACM, vol. 22, no. 5, pp. 281–283, May 1979. DOI: 10.1145/359104.359108
[2] D. S. Hirschberg and J. B. Sinclair, “Decentralized extrema-finding in circular configurations of processors,” Communications of the ACM, vol. 23, no. 11, pp. 627–628, Nov. 1980. DOI: 10.1145/359024.359029
[3] H. Garcia-Molina, “Elections in a distributed computing system,” IEEE Transactions on Computers, vol. C-31, no. 1, pp. 48–59, Jan. 1982. DOI: 10.1109/TC.1982.1675885
[4] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” Journal of the ACM, vol. 32, no. 2, pp. 374–382, Apr. 1985. DOI: 10.1145/3149.214121
[5] L. Lamport, “The part-time parliament,” ACM Transactions on Computer Systems, vol. 16, no. 2, pp. 133–169, May 1998. DOI: 10.1145/279227.279229
[6] L. Lamport, “Paxos made simple,” ACM SIGACT News, vol. 32, no. 4, pp. 18–25, Dec. 2001. Available: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[7] D. Ongaro and J. Ousterhout, “In search of an understandable consensus algorithm,” in Proc. 2014 USENIX Annual Technical Conference (USENIX ATC ’14), Philadelphia, PA, Jun. 2014, pp. 305–319. Available: https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
[8] F. P. Junqueira, B. C. Reed, and M. Serafini, “Zab: High-performance broadcast for primary-backup systems,” in Proc. IEEE/IFIP 41st International Conference on Dependable Systems and Networks (DSN), Jun. 2011, pp. 245–256. DOI: 10.1109/DSN.2011.5958223
[9] P. Hunt, M. Konar, F. P. Junqueira, and B. Reed, “ZooKeeper: Wait-free coordination for internet-scale systems,” in Proc. 2010 USENIX Annual Technical Conference, Jun. 2010, pp. 145–158. Available: https://www.usenix.org/legacy/event/atc10/tech/full_papers/Hunt.pdf
[10] T. D. Chandra and S. Toueg, “Unreliable failure detectors for reliable distributed systems,” Journal of the ACM, vol. 43, no. 2, pp. 225–267, Mar. 1996. DOI: 10.1145/226643.226647
[11] G. L. Peterson, “An O(n log n) unidirectional algorithm for the circular extrema problem,” ACM Transactions on Programming Languages and Systems, vol. 4, no. 4, pp. 758–762, Oct. 1982. DOI: 10.1145/69622.357194
[12] D. Dolev, M. Klawe, and M. Rodeh, “An O(n log n) unidirectional distributed algorithm for extrema finding in a circle,” Journal of Algorithms, vol. 3, no. 3, pp. 245–260, Sep. 1982. DOI: 10.1016/0196-6774(82)90023-2
[13] G. Le Lann, “Distributed systems - towards a formal approach,” in IFIP Congress, Toronto, 1977, pp. 155–160.
[14] N. A. Lynch, Distributed Algorithms. San Francisco, CA: Morgan Kaufmann, 1996.
[15] D. Ongaro, “Consensus: Bridging theory and practice,” Ph.D. dissertation, Stanford University, Stanford, CA, 2014. Available: https://web.stanford.edu/~ouster/cgi-bin/papers/OnsaroPhD.pdf
[16] B. Reed and F. P. Junqueira, “A simple totally ordered broadcast protocol,” in Proc. 2nd Workshop on Large-Scale Distributed Systems and Middleware (LADIS), 2008.
[17] D. Dolev, C. Dwork, and L. Stockmeyer, “On the minimal synchronism needed for distributed consensus,” Journal of the ACM, vol. 34, no. 1, pp. 77–97, Jan. 1987. DOI: 10.1145/7531.7533
[18] etcd Authors, “etcd: A distributed, reliable key-value store,” 2024. Available: https://etcd.io/
[19] HashiCorp, “Consul: Service mesh and service discovery,” 2024. Available: https://www.consul.io/
[20] Apache Software Foundation, “Apache ZooKeeper,” 2024. Available: https://zookeeper.apache.org/
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Yevhen Piotrovskyi
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who submit papers with this journal agree to the following terms.
