Skip to main content
SpringerLink
Log in

Design and analysis of dynamic leader election protocols in broadcast networks

  • Published:
Distributed Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abu-Amara HH: Fault-tolerant distributed algorithm for election in complete networks. IEEE Trans Comput 37: 449–453 (1988)

    Article  MATH  Google Scholar 

  2. Afek Y, Gafni E: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J Comput 20: 376–394 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  3. 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

    Google Scholar 

  4. Attiya H, van Leeuwen J, Santoro N, Zaks S: Efficient elections in chordal ring networks. Algorithmica 4: 437–446 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  5. Baeten JCM, Weijland WP: Process algebra. Cambridge Tracts in Theoretical Computer Science, vol 18, Cambridge University Press 1990

  6. von Bochmann G: Finite state description of communication protocols. Comput Networks 2: 361–372 (1978)

    Google Scholar 

  7. Brunekreef JJ: On modular algebraic protocol specification. PhD thesis, University of Amsterdam, The Netherlands 1995

    Google Scholar 

  8. 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)

    Google Scholar 

  9. 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

    Google Scholar 

  10. Budkowski S, Dembinski P: An introduction to Estelle: a specification language for distributed systems. Comput Networks ISDN Syst 14: 3–23 (1987)

    Article  Google Scholar 

  11. Chang E, Roberts R: An improved algorithm for decentralized extrema-finding in circular configurations of processors. Commun ACM 22: 281–283 (1979)

    Article  MATH  Google Scholar 

  12. 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

    Google Scholar 

  13. 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

    Google Scholar 

  14. Dolev D, Dwork C, Stockmeyer L: On the minimal synchronism needed for distributed consensus. J ACM 34: 77–97 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  15. Dijkstra EW: Self-stabilizing systems in spite of distributed control. Commun ACM 17: 634–644 (1974)

    Article  Google Scholar 

  16. 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

    Google Scholar 

  17. Gehani NH: Broadcasting sequential processes. IEEE Trans Softw Eng 10: 343–351 (1984)

    Article  Google Scholar 

  18. Gotzhein R: Temporal logic and its applications — a tutorial. Comput Networks ISDN Syst 24: 203–218 (1992)

    Article  MATH  Google Scholar 

  19. Gouda MG: Protocol verification made simple: a tutorial. Comput Networks ISDN Syst 25: 969–980 (1993)

    Article  Google Scholar 

  20. 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

  21. Hailpern BT, Owicki SS: Modular verification of computer communication protocols. IEEE Trans Commun 31: 56–68 (1983)

    Article  Google Scholar 

  22. Hoare CAR: Communicating sequential processes. Prentice-Hall, Englewood Cliffs 1985

    MATH  Google Scholar 

  23. Itai A, Kutten S, Wolfstahl Y, Zaks S: Optimal distributed r-resilient election in complete networks. IEEE Trans Softw Eng 16: 415–420 (1990)

    Article  Google Scholar 

  24. King C-T, Gendreau TB, Ni LM: Reliable election in broadcast networks. J Parallel Distrib Comput 7: 521–540 (1989)

    Article  Google Scholar 

  25. 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)

    Article  Google Scholar 

  26. 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

  27. 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

    Google Scholar 

  28. Lamport L: Specifying concurrent program modules. ACM Trans Prog Lang Syst 5: 190–222 (1983)

    Article  MATH  Google Scholar 

  29. Larsen KG, Thomsen B: A modal process logic. In: Proc IEEE Symposium on Logic in Computer Science (1988), pp 203–210

  30. van Leeuwen J, Tan RB: An improved upperbound for distributed election in bidirectional rings of processors. Distrib Comput 2: 149–160 (1987)

    Article  Google Scholar 

  31. LeLann, G: Distributed systems — towards a formal approach. In: Gilchrist B (ed) Information Processing (vol. 77) (IFIP). North-Holland, Amsterdam 1977, pp 155–160

    Google Scholar 

  32. 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))

    Article  MathSciNet  Google Scholar 

  33. Manna Z, Pnueli A: The temporal logic of reactive and concurrent systems — Specification. Springer, Berlin Heidelberg New York 1992

    Google Scholar 

  34. 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

    Google Scholar 

  35. Mauw S, Veltink G: A process specification formalism. Fund Inf VIII: 85–139 (1990)

    Google Scholar 

  36. Melliar-Smith PM, Moser LE, Agrawala V: Broadcast protocols for distributed systems. IEEE Trans Parallel Distrib Syst 1: 17–25 (1990)

    Article  Google Scholar 

  37. Peterson GL: An O(nlogn) unidirectional algorithm for the circular extrema problem. ACM Trans Program Lang Syst 4: 758–762 (1982)

    Article  MATH  Google Scholar 

  38. Schneider M: Self-stabilization. ACM Comput Surv 25: 45–67 (1993)

    Article  Google Scholar 

  39. Schneider FB, Gries D, Schlichting RD: Fault-tolerant broadcasts. Sci Comput Program 4: 1–16 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  40. 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

  41. Shrira L, Goldreich O: Electing a leader in a ring with link failures. Acta Inf 24: 79–91 (1989)

    MathSciNet  Google Scholar 

  42. 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

Download references

Author information

Authors and Affiliations

  1. Programming Research Group, University of Amsterdam, Kruislaan 403, 1098, Amsterdam, SJ, The Netherlands

    Jacob Brunekreef

  2. Department of Computing Science, University of Twente, P.O. Box 217, 7500, Enschede, AE, The Netherlands

    Joost-Pieter Katoen

  3. Philips Research Laboratories, Prof. Holstlaan 4, 5656, Eindhoven, AA, The Netherlands

    Ron Koymans

  4. Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600, Eindhoven, MB, The Netherlands

    Sjouke Mauw

Authors
  1. Jacob Brunekreef
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joost-Pieter Katoen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ron Koymans
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sjouke Mauw
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s004460050017

Key words

Search

Navigation