Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 5/2018

08-04-2017

Self-Stabilizing Leader Election in Dynamic Networks

Authors: Ajoy K. Datta, Lawrence L. Larmore

Published in: Theory of Computing Systems | Issue 5/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Two silent self-stabilizing asynchronous distributed algorithms are given for the leader election problem in a dynamic network with unique IDs. A leader is elected for each connected component of the network. A BFS DAG, rooted at the leader, is constructed in each component. The construction takes O(D i a m) rounds, where D i a m is the maximum diameter of any component. Both algorithms are self-stabilizing, silent, and work under the unfair daemon, but use one unbounded integer variable. Algorithm DLE selects an arbitrary process to be the leader of each component. Algorithm DLEND (Distributed Leader Election No Dithering) has the incumbency property and the no dithering property. If the configuration is legitimate and a topological fault occurs, each component will elect, if possible, an incumbent to be its leader, i.e., a process which was a leader before the fault. Furthermore, during this computation, no process will change its choice of leader more than once.
next article Exact Localisations of Feedback Sets

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
1.
Afek, Y., Bremler, A.: Self-Stabilizing Unidirectional Network Algorithms by Power-Supply (Extended Abstract) SODA, pp 111–120 (1997)
2.
Afek, Y., Kutten, S., Yung, M.: The Local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186, 199–229 (1997)MathSciNetCrossRefMATH
3.
Aggarwal, S., Kutten, S.: Time-Optimal Self-Stabilizing Spanning Tree Algorithms Proceedings of the 13 t H Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS ’93), pp 400–410 (1993)CrossRef
4.
5.
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: Time Optimal Self-Stabilizing Synchronization Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC ’93), pp 652–661 (1993)
6.
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: A Time-optimal self-stabilizing synchronizer using a phase clock. IEEE Trans, Dependable Sec. Comput. 4(3), 180–190 (2007)CrossRef
7.
Awerbuch, B., Richa, A.W., Scheideler, Christian: A Jamming-resistant Mac Protocol for Single-Hop Wireless Networks PODC, pp 45–54 (2008)
8.
Brunekreef, J., Katoen, J.-P., Koymans, R., Mauw, S.: Design and analysis of dynamic leader election protocols in broadcast networks. Distrib. Comput. 9(4), 157–171 (1996)CrossRef
9.
Datta, A.K., Larmore, L.L., Piniganti, H.: Self-Stabilizing Leader Election in Dynamic Networks 12Th International Symposium on Stabilization, Safety, and Security of Distributed Systems(SSS), pp 35–49 (2010)CrossRef
10.
Datta, A.K., Larmore, L.L., Vemula, P.: An O(n)-time self-stabilizing leader election algorithm. J. Parallel Distrib. Comput. 71(11), 1532–1544 (2011)CrossRefMATH
11.
Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space under an arbitrary scheduler. Theor. Comput. Sci. 412(40), 5541–5561 (2011)MathSciNetCrossRefMATH
12.
Derhab, A., Badache, N.: A Self-stabilizing leader election algorithm in highly dynamic ad hoc mobile networks. IEEE Trans. Parallel Distrib. Syst. 19(7), 926–939 (2008)CrossRefMATH
13.
Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Commun. ACM 17, 643–644 (1974)CrossRefMATH
14.
Dolev, S.: Self-Stabilization. The MIT Press (2000)
15.
Dolev, S., Herman, T.: Superstabilizing protocols for dynamic distributed systems. Chicago J. Theor Comput. Sci., 1997 (1997)
16.
Fetzer, C., Cristian, F.: A Highly available local leader election service. IEEE Trans. Software Eng. 25(5), 603–618 (1999)CrossRef
17.
Gafni, E., Bertsekas, D.P.: Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Trans. Commun. C-29 (1), 11–18 (1981)MathSciNetCrossRef
18.
Gouda, M.G., Multari, N.J.: Stabilizing communication protocols. IEEE Trans. Computers 40(4), 448–458 (1991)CrossRef
19.
Haas, Z.J.: A New Routing Protocol for the Reconfigurable Wireless Networks. In: 6Th International Conference on Universal Personal Communications Record, 1997. Conference Record., vol. 2 pp. 562–566. IEEE (1997)
20.
Hatzis, K.P., Pentaris, G.P., Spirakis, P.G., Tampakas, V.T., Tan, Richard B.: Fundamental Control Algorithms in Mobile Networks SPAA, pp 251–260 (1999)
21.
Ingram, R., Radeva, T., Shields, P., Viqar, S., Walter, J.E., Welch, J.L.: A Leader election algorithm for dynamic networks with causal clocks. Distrib. Comput. 26(2), 75–97 (2013)CrossRefMATH
22.
Ingram, R., Shields, P., Walter, J.E., Welch, J.L.: An Asynchronous Leader Election Algorithm for Dynamic Networks IPDPS, pp 1–12 (2009)
23.
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRefMATH
24.
Malpani, N., Welch, J.L., Vaidya, N.H.: Leader Election Algorithms for Mobile Ad Hoc Networks DIAL-M, pp 96–103 (2000)
25.
Mans, B., Santoro, N.: Optimal elections in faulty loop networks and applications. IEEE Trans. Computers 47(3), 286–297 (1998)MathSciNetCrossRef
26.
Masum, S.M., Ali, A.A., Bhuiyan, Mohammad Touhid-youl Islam: Asynchronous Leader Election in Mobile Ad Hoc Networks AINA, vol. 2, pp 827–831 (2006)
27.
Yi, P., Singh, G.: A Fault-tolerant protocol for election in chordal-ring networks with fail-stop processor failures. IEEE Trans. Reliab. 46(1), 11–17 (1997)CrossRef
28.
Parvathipuram, P., Kumar, V., Yang, G.-C.: An Efficient Leader Election Algorithm for Mobile Ad Hoc Networks. In: ICDCIT (2004)
29.
Singh, G.: Leader election in the presence of link failures. IEEE Trans. Parallel Distrib. Syst. 7(3), 231–236 (1996)CrossRef
30.
Stoller, S.D.: Leader election in distributed systems with crash failures. S. Stoller. Leader election in distributed systems with crash failures. Technical report. Indiana University 169, 1997 (1997)
31.
Vasudevan, S., Kurose, J.F., Towsley, D.F.: Design and Analysis of a Leader Election Algorithm for Mobile Ad Hoc Networks ICNP, pp 350–360 (2004)
Metadata
Title
Self-Stabilizing Leader Election in Dynamic Networks
Authors
Ajoy K. Datta
Lawrence L. Larmore
Publication date
08-04-2017
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 5/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-017-9758-9

Other articles of this Issue 5/2018

Theory of Computing Systems 5/2018 Go to the issue

OriginalPaper

On Effective Birkhoff’s Ergodic Theorem for Computable Actions of Amenable Groups

Publisher Correction

Publisher Correction: Editor’s Note

OriginalPaper

A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games

OriginalPaper

Collaborative Exploration of Trees by Energy-Constrained Mobile Robots

OriginalPaper

Exact Localisations of Feedback Sets

OriginalPaper

Bounded-Depth Succinct Encodings and the Structure they Imply on Graphs

Premium Partner

    Image Credits