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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Fast Two-Robot Disk Evacuation with Wireless Communication Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Are Byzantine Failures Really Different from Crash Failures?

verfasst von : Damien Imbs, Michel Raynal, Julien Stainer

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

When considering n-process asynchronous systems, where up to t processes can fail, and communication is by read/write registers or reliable message-passing, are (from a computability point of view) Byzantine failures “different” from crash failures? This is the question addressed in this paper, which shows that the answer is “no” for systems where \(t<n/3\).
To this end, the paper presents a new distributed simulation whose core is an extended BG simulation suited to asynchronous message-passing systems. More precisely, assuming \(t<\min (n',n/3)\), it describes a signature-free algorithm that simulates a system of \(n'\) processes where up to t may crash, on top of a basic system of n processes where up to t may be Byzantine. In addition to extending (in a modular and direct way) the basic BG simulation to Byzantine message-passing systems this simulation also allows crash-tolerant algorithms, designed for asynchronous read/write systems, to be executed on top of asynchronous message-passing systems prone to Byzantine failures.

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 Non-local Probes Do Not Help with Many Graph Problems
Nächstes Kapitel Sublinear-Space Distance Labeling Using Hubs
Fußnoten
1
Independently from our work, a concurrent work by Dolev and Gafni [5] (based on a totally different approach) shows a result similar to ours, namely, a system with \(t<n/3\) Byzantine processes can neutralize the Byzantine processes to appear as a t-resilient system (with respect to crash failures). Hence, both papers show that “the difficulty of distributed computing is captured solely by crash failures”. Consequently, according to an implicit suggestion appearing in a referee report, the title of the current proceedings version has been modified (with respect to the title of the submitted version [8]) to emphasize this important observation.
 
Literatur
1.
Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message passing systems. J. ACM 42(1), 121–132 (1995)CrossRefMATH
2.
Bazzi, R., Neiger, G.: Optimally simulating crash failures in a byzantine environment. In: Toueg, S., Spirakis, P.G., Kirousis, L. (eds.) Distributed Algorithms. LNCS, vol. 579, pp. 108–128. Springer, Heidelberg (1991)CrossRef
3.
Borowsky, E., Gafni, E.: Generalized FLP impossibility results for \(t\)-resilient asynchronous computations. In: Proceedings 25th ACM STOC, pp. 91–100. ACM Press (1993)
4.
Coan, B.A.: A compiler that increases the fault-tolerance of asynchronous protocols. IEEE Trans. Comput. 37(12), 1541–1553 (1988)MathSciNetCrossRefMATH
5.
Dolev, D., Gafni, E.: Some garbage in - some garbage out,: asynchronous \(t\)-Byzantine as asynchronous benign \(t\)-resilient system with fixed \(t\)-Trojan horse inputs. Tech Report, arXiv, 14 p., July 2016. arXiv:​1607.​01210
6.
Herlihy, M.P., Kozlov, D., Rajsbaum, S.: Distributed Computing through Combinatorial Topology, p. 336. Morgan Kaufmann/Elsevier, New York (2014). (ISBN 9780124045781)MATH
7.
Ho, C., Dolev, D., van Renesse, R.: Making distributed applications robust. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 232–246. Springer, Heidelberg (2007)CrossRef
8.
Imbs, D., Raynal, M., Stainer, J., Byzantine, F.: Failures to crash failures in message-passing systems: a BG simulation-based approach. Technical Report, arXiv, 27 p., October 2015. arXiv:​1510.​09119
9.
Lamport, L., Shostack, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRefMATH
10.
Mendes, H., Tasson Ch., Herlihy, M.: Distributed computability in Byzantine asynchronous systems. In: Proceedings 46th STOC, pp. 704–713. ACM Press (2014)
11.
Neiger, G., Toueg, S.: Automatically increasing the fault-tolerance of distributed algorithms. J. Algorithms 11(3), 374–419 (1990)MathSciNetCrossRefMATH
12.
Srikanth, T.K., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Comput. 2(2), 80–94 (1987)CrossRef
Metadaten
Titel
Are Byzantine Failures Really Different from Crash Failures?
verfasst von
Damien Imbs
Michel Raynal
Julien Stainer
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_16

Premium Partner

    Bildnachweise