Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Fast Two-Robot Disk Evacuation with Wireless Communication Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Anonymity-Preserving Failure Detectors

verfasst von : Zohir Bouzid, Corentin Travers

Erschienen in: Distributed Computing

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The paper investigates the consensus problem in anonymous, failures prone and asynchronous shared memory systems. It introduces a new class of failure detectors, called anonymity-preserving failure detectors suited to anonymous systems. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP, which gives at each process an estimation of the number of processes that have failed belongs to this class.
The paper then determines the weakest failure detector among this class for consensus. This failure detector, called \(C \), may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) if two or more processes are non-faulty, it eventually stabilizes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
Nächstes Kapitel Certified Universal Gathering in for Oblivious Mobile Robots
Fußnoten
1
More generally, v may belong to any finite set. Restricting to binary inputs is sufficient for our purpose, namely using failure detector \(C \) to solve binary consensus.
 
Literatur
1.
Angluin, D.: Local and global properties in networks of processors (extended abstract). In: STOC 1980, pp. 82–93. ACM (1980)
2.
Aspnes, J.: A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Distributed Comput. 25(2), 179–188 (2012)CrossRefMATH
3.
4.
Attiya, H.: Adapting to point contention with long-lived safe agreement. In: Flocchini, P., Gasieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 10–23. Springer, Heidelberg (2006)CrossRef
5.
Attiya, H., Gorbach, A., Moran, S.: Computing in totally anonymous asynchronous shared memory systems. Inf. Comput. 173(2), 162–183 (2002)MathSciNetCrossRefMATH
6.
7.
Bonnet, F., Raynal, M.: Consensus in anonymous distributed systems: Is there a weakestfailure detector? In: AINA 2010, pp. 206–213. IEEE (2010)
8.
Bonnet, F., Raynal, M.: Anonymous asynchronous systems: the case of failure detectors. Distributed Comput. 26(3), 141–158 (2013)CrossRefMATH
9.
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronouscomputations. In: PODC 1993, pp. 91–100. ACM (1993)
10.
Borowsky, E., Gafni, E., Lynch, N.A., Rajsbaum, S.: The BG distributed simulation algorithm. Distributed Comput. 14(3), 127–146 (2001)CrossRef
11.
12.
13.
14.
Danezis, G., Diaz, C.: A survey of anonymous communication channels. Technical Report, MSR-TR-2008-35, Microsoft Research (2008)
15.
Delporte-Gallet, C., Fauconnier, H.: Two consensus algorithms with atomic registers and failure detector \(\Omega \). In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol. 5408, pp. 251–262. Springer, Heidelberg (2008)CrossRef
16.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: Tight failure detection bounds on atomic object implementations. J. ACM 57(4), 22:1–22:32 (2010)MathSciNetMATH
17.
18.
Freiling, F.C., Guerraoui, R., Kuznetsov, P.: The failure detector abstraction. ACM Comput. Surv. 43(2), 9 (2011)CrossRefMATH
19.
Gafni, E.: Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract). In: PODC 1998, pp. 143–152. ACM (1998)
20.
Gafni, E.: The extended BG-simulation and the characterization of \(t\)-resiliency. In: STOC 1909, pp. 85–92. ACM (1990)
21.
Gafni, E., Kuznetsov, P.: On set consensus numbers. Distributed Comput. 24(3–4), 149–163 (2011)CrossRefMATH
22.
Guerraoui, R., Hadzilacos, V., Kuznetsov, P., Toueg, S.: The weakest failure detectors to solve quittable consensus and nonblocking atomic commit. SIAM J. Comput. 41(6), 1343–1379 (2012)MathSciNetCrossRefMATH
23.
Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distributed Comput. 20(3), 165–177 (2007)CrossRefMATH
24.
Loui, M., Abu-Amara, H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163–183 (1987)MathSciNet
25.
Yamashita, M., Kameda, T.: Computing on anonymous networks: Part I-characterizing the solvable cases. Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996)CrossRef
26.
Zieliński, P.: Anti-\(\varOmega \): the weakest failure detector for set agreement. Distributed Comput. 22(5–6), 335–348 (2010)CrossRefMATH
Metadaten
Titel
Anonymity-Preserving Failure Detectors
verfasst von
Zohir Bouzid
Corentin Travers
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Distributed Computing

Print ISBN: 978-3-662-53425-0

Electronic ISBN: 978-3-662-53426-7

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53426-7_13