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 2/2019

23-02-2018

Packet Efficient Implementation of the Omega Failure Detector

Authors: Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil

Published in: Theory of Computing Systems | Issue 2/2019

Log in

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

search-config
loading …

Abstract

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. To motivate the study, we prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation. An implementation is: message efficient if all but finitely many messages are sent by a single process; packet efficient if it is message efficient and the number of packets used to transmit all but finitely many messages is proportional to the number of processes in the system; super packet efficient if it is message efficient and the number of channels used to transmit all but finitely many packets is proportional to the number of processes in the system. We prove that a super packet efficient implementation of Omega is impossible. We establish necessary conditions for the existence of a packet efficient implementation of Omega and present an algorithm that implements Omega under these conditions.
previous article Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model
next article Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

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
Footnotes
1
In literature, the detector is usually denoted by the Greek letter. However, we use the letter to denote the complexity lower bound. To avoid confusion, we spell out the name of the failure detector in English.
 
2
x ∼ y means that x approaches y as \(n \rightarrow \infty \).See [17] for usage.
 
Literature
1.
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Communication-efficient leader election and consensus with limited link synchrony. In: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pp. 328–337. ACM (2004)
2.
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: On implementing omega in systems with weak reliability and synchrony assumptions. Distrib. Comput. 21(4), 285–314 (2008)CrossRefMATH
3.
Anta, A.F., Raynal, M.: From an asynchronous intermittent rotating star to an eventual leader. IEEE Trans. Parallel Distrib. Syst 21(9), 1290–1303 (2010)CrossRef
4.
Arantes, L., Greve, F., Sens, P., Simon, V.: Eventual leader election in evolving mobile networks. In: International Conference on Principles of Distributed Systems (OPODIS), vol. 8304, pp. 23–37 (2013)
5.
Biely, M., Widder, J.: Optimal message-driven implementations of omega with mute processes. ACM Trans. Auto. Adaptive Syst. 4(1), 4 (2009)
6.
7.
8.
9.
Chandy, K.M., Misra, J.: Parallel program design: A Foundation. Addison-Wesley, Boston (1988)MATH
10.
Charron-Bost, B., Függer, M., Nowak, T.: Approximate consensus in highly dynamic networks. arXiv:1408.​0620 (2014)
11.
Delporte-Gallet, C., Devismes, S., Fauconnier, H.: Robust stabilizing leader election. In: Symposium on Self-Stabilizing Systems, pp. 219–233. Springer (2007)
12.
Delporte-Gallet, C., Devismes, S., Fauconnier, H., Larrea, M.: Algorithms for extracting timeliness graphs. In: Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings, pp. 127–141 (2010)
13.
14.
Fernȧndez, A., Jimėnez, E., Raynal, M.: Eventual leader election with weak assumptions on initial knowledge, communication reliability, and synchrony. In: International Conference on Dependable Systems and Networks (DSN’06), pp. 166–178. IEEE (2006)
15.
Fernández-Campusano, C., Larrea, M., Cortiñas, R., Raynal, M.: A communication-efficient leader election algorithm in partially synchronous systems prone to crash-recovery and omission failures. In: Proceedings of the 17th International Conference on Distributed Computing and Networking, p. 8. ACM (2016)
16.
17.
18.
Hutle, M., Malkhi, D., Schmid, U., Zhou, L.: Chasing the weakest system model for implementing ω and consensus. IEEE Trans. Dependable Sec. Comput. 6(4), 269–281 (2009)CrossRef
19.
Jiménez, E., Arévalo, S., Fernández, A.: Implementing unreliable failure detectors with unknown membership. Inf. Process. Lett. 100(2), 60–63 (2006)MathSciNetCrossRefMATH
20.
Lafuente, A., Larrea, M., Soraluze, I., Cortiñas, R.: Communication-optimal eventually perfect failure detection in partially synchronous systems. J. Comput. Syst. Sci. 81(2), 383–397 (2015)MathSciNetCrossRefMATH
21.
Larrea, M., Fernȧndez, A., Arėvalo, S.: On the implementation of unreliable failure detectors in partially synchronous systems. IEEE Trans. Comput. 53(7), 815–828 (2004)CrossRef
22.
Malkhi, D., Oprea, F., Zhou, L.: Ω meets paxos: Leader election and stability without eventual timely links. In: Distributed Computing, pp. 199–213. Springer (2005)
23.
Mostefaoui, A., Mourgaya, E., Raynal, M.: Asynchronous implementation of failure detectors. In: 2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 351–351. IEEE Computer Society (2003)
24.
Mostėfaoui, A., Raynal, M., Travers, C.: Time-free and timer-based assumptions can be combined to obtain eventual leadership. IEEE Trans. Parallel Distrib. Syst. 17(7), 656–666 (2006)CrossRef
25.
Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)
26.
Metadata
Title
Packet Efficient Implementation of the Omega Failure Detector
Authors
Quentin Bramas
Dianne Foreback
Mikhail Nesterenko
Sébastien Tixeuil
Publication date
23-02-2018
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 2/2019
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-018-9856-3

Other articles of this Issue 2/2019

Theory of Computing Systems 2/2019 Go to the issue

OriginalPaper

On-Line Path Computation and Function Placement in SDNs

OriginalPaper

Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model

OriginalPaper

Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

OriginalPaper

Synchronous Gathering without Multiplicity Detection: a Certified Algorithm

OriginalPaper

Self-Stabilizing Metric Graphs

OriginalPaper

Making Local Algorithms Wait-Free: the Case of Ring Coloring

Premium Partner

    Image Credits