Summary
The well-known problem of leader election in distributed systems is considered in a dynamic context where processes may participate and crash spontaneously. Processes communicate by means of buffered broadcasting as opposed to usual point-to-point communication. In this paper we design a leader election protocol in such a dynamic context. As the problem at hand is considerably complex we develop the protocol in three steps. In the initial design processes are considered to be perfect and a leader is assumed to be present initially. In the second protocol, the assumption of an initial leader is dropped. This leads to a symmetric protocol which uses an (abstract) timeout mechanism to detect the absence of a leader. Finally, in the last step of the design processes may crash without giving any notification of other processes. The worst case message complexity of all protocols is addressed. A formal approach to the specification and verification of the leader election protocols is adopted. The requirements are specified in a property-oriented way and the protocols are denoted by means of extended finite state machines. It is proven using linear-time temporal logic that the fault-tolerant protocol satisfies its requirements.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abu-Amara HH: Fault-tolerant distributed algorithm for election in complete networks. IEEE Trans Comput 37: 449–453 (1988)
Afek Y, Gafni E: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J Comput 20: 376–394 (1991)
Attiya H: Constructing efficient election algorithms from efficient traversal algorithms. In: van Leeuwen J (ed) Distributed algorithms. Lect Notes Comput Sci, vol 312. Springer, Berlin Heidelberg New York 1987, pp 337–344
Attiya H, van Leeuwen J, Santoro N, Zaks S: Efficient elections in chordal ring networks. Algorithmica 4: 437–446 (1989)
Baeten JCM, Weijland WP: Process algebra. Cambridge Tracts in Theoretical Computer Science, vol 18, Cambridge University Press 1990
von Bochmann G: Finite state description of communication protocols. Comput Networks 2: 361–372 (1978)
Brunekreef JJ: On modular algebraic protocol specification. PhD thesis, University of Amsterdam, The Netherlands 1995
Brunekreef JJ, Katoen J-P, Koymans RLC, Mauw S: Design and analysis of dynamic leader election protocols in broadcast networks. Memoranda Informatica 93–43, Department of Computer Science, University of Twente, The Netherlands (1993)
Brunekreef JJ, Katoen J-P, Koymans RLC, Mauw S: Algebraic specification of dynamic leader election protocols in broadcast networks. In: Ponse A, Verhoef C, van Vlijmen SFM (eds) Algebra of communicating processes. Workshops in Computing, Springer, Berlin Heidelberg New York 1994, pp 338–357
Budkowski S, Dembinski P: An introduction to Estelle: a specification language for distributed systems. Comput Networks ISDN Syst 14: 3–23 (1987)
Chang E, Roberts R: An improved algorithm for decentralized extrema-finding in circular configurations of processors. Commun ACM 22: 281–283 (1979)
Dolev S: Optimal time self stabilization in dynamic systems. In: Schiper A (ed) Distributed algorithms. Lect Notes Comput Sci, vol 725. Springer, Berlin Heidelberg New York 1993, pp 160–173
Dolev S, Israeli A, Moran S: Uniform dynamic self-stabilizing leader election. In: Toueg S et al (eds) Distributed algorithms. Lect Notes Comput Sci, vol 579. Springer, Berlin Heidelberg New York 1992, pp 167–180
Dolev D, Dwork C, Stockmeyer L: On the minimal synchronism needed for distributed consensus. J ACM 34: 77–97 (1987)
Dijkstra EW: Self-stabilizing systems in spite of distributed control. Commun ACM 17: 634–644 (1974)
Fisher MJ: A theoretician’s view of fault-tolerant distributed computing. In: Simons B, Spector A (eds) Fault-tolerant distributed computing. Lect Notes Comput Sci, vol 448. Springer, Berlin Heidelberg New York 1991, pp 1–9
Gehani NH: Broadcasting sequential processes. IEEE Trans Softw Eng 10: 343–351 (1984)
Gotzhein R: Temporal logic and its applications — a tutorial. Comput Networks ISDN Syst 24: 203–218 (1992)
Gouda MG: Protocol verification made simple: a tutorial. Comput Networks ISDN Syst 25: 969–980 (1993)
Gusella R, Zatti S: An election algorithm for a distributed clock synchronization program. In: Proc 6th IEEE Int Conf on Distributed Computing Systems (1986), pp 364–371
Hailpern BT, Owicki SS: Modular verification of computer communication protocols. IEEE Trans Commun 31: 56–68 (1983)
Hoare CAR: Communicating sequential processes. Prentice-Hall, Englewood Cliffs 1985
Itai A, Kutten S, Wolfstahl Y, Zaks S: Optimal distributed r-resilient election in complete networks. IEEE Trans Softw Eng 16: 415–420 (1990)
King C-T, Gendreau TB, Ni LM: Reliable election in broadcast networks. J Parallel Distrib Comput 7: 521–540 (1989)
Korach E, Kutten S, Moran S: A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans Prog Lang Syst 12: 84–101 (1990)
Korach E, Moran S, Zaks S: Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In: Proc ACM Symp Principles Distributed Comput (1984), pp 199–207
Koymans RLC: Specifying message passing systems requires extending temporal logic. In: Banieqbal B et al (eds) Proc Colloquium on Temporal Logic and Specification. Lect Notes Comput Sci, vol 398. Springer, Berlin Heidelberg New York 1989, pp 213–223
Lamport L: Specifying concurrent program modules. ACM Trans Prog Lang Syst 5: 190–222 (1983)
Larsen KG, Thomsen B: A modal process logic. In: Proc IEEE Symposium on Logic in Computer Science (1988), pp 203–210
van Leeuwen J, Tan RB: An improved upperbound for distributed election in bidirectional rings of processors. Distrib Comput 2: 149–160 (1987)
LeLann, G: Distributed systems — towards a formal approach. In: Gilchrist B (ed) Information Processing (vol. 77) (IFIP). North-Holland, Amsterdam 1977, pp 155–160
Loui MC, Matsushita TA, West DB: Election in a complete network with a sense of direction. Inf Process Lett 22: 185–187 (1986) (correction in Inf Process Letters 28: 327 (1988))
Manna Z, Pnueli A: The temporal logic of reactive and concurrent systems — Specification. Springer, Berlin Heidelberg New York 1992
Masuzawa T, Nishikawa N, Hagihara K. Tokura N: Optimal fault-tolerant distributed algorithms for election in complete networks with a global sense of direction. In: Bermond J-C, Raynal M (eds) Distributed algorithms. Lect Notes Comput Sci. vol 392, Springer, Berlin Heidelberg New York 1989, pp 171–182
Mauw S, Veltink G: A process specification formalism. Fund Inf VIII: 85–139 (1990)
Melliar-Smith PM, Moser LE, Agrawala V: Broadcast protocols for distributed systems. IEEE Trans Parallel Distrib Syst 1: 17–25 (1990)
Peterson GL: An O(nlogn) unidirectional algorithm for the circular extrema problem. ACM Trans Program Lang Syst 4: 758–762 (1982)
Schneider M: Self-stabilization. ACM Comput Surv 25: 45–67 (1993)
Schneider FB, Gries D, Schlichting RD: Fault-tolerant broadcasts. Sci Comput Program 4: 1–16 (1984)
Shasha DE, Pnueli A, Ewald W: Temporal verification of carrier-sense local area network protocols. In: Proc ACM Symposium on Principles of Programming Languages (1984), pp 54–65
Shrira L, Goldreich O: Electing a leader in a ring with link failures. Acta Inf 24: 79–91 (1989)
Singh G: Efficient distributed algorithms for leader election in complete networks. In: Proc 11th IEEE Int Conf on Distributed Computing Systems (1991), pp 472–479
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Brunekreef, J., Katoen, JP., Koymans, R. et al. Design and analysis of dynamic leader election protocols in broadcast networks. Distrib Comput 9, 157–171 (1996). https://doi.org/10.1007/s004460050017
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s004460050017