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
Distributed Computing
Erschienen in: Distributed Computing 6/2022

02.09.2022

Making Byzantine consensus live

verfasst von: Manuel Bravo, Gregory Chockler, Alexey Gotsman

Erschienen in: Distributed Computing | Ausgabe 6/2022

Einloggen

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

search-config
loading …

Abstract

Partially synchronous Byzantine consensus protocols typically structure their execution into a sequence of views, each with a designated leader process. The key to guaranteeing liveness in these protocols is to ensure that all correct processes eventually overlap in a view with a correct leader for long enough to reach a decision. We propose a simple view synchronizer abstraction that encapsulates the corresponding functionality for Byzantine consensus protocols, thus simplifying their design. We present a formal specification of a view synchronizer and its implementation under partial synchrony, which runs in bounded space despite tolerating message loss during asynchronous periods. We show that our synchronizer specification is strong enough to guarantee liveness for single-shot versions of several well-known Byzantine consensus protocols, including PBFT and HotStuff. We furthermore give precise latency bounds for these protocols when using our synchronizer. By factoring out the functionality of view synchronization we are able to specify and analyze the protocols in a uniform framework, which allows comparing them and highlights trade-offs.
Vorheriger Artikel Asynchronous reconfiguration with Byzantine failures
Nächster Artikel Linial for lists

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Synchronous Byzantine agreement with expected \({O}(1)\) rounds, expected \({O}(n^2)\) communication, and optimal resilience. In: Conference on Financial Cryptography and Data Security (FC) (2019)
2.
Abraham, I., Gueta, G., Malkhi, D., Alvisi, L., Kotla, R., Martin, J.: Revisiting fast practical Byzantine fault tolerance. arXiv:​1712.​01367 (2017)
3.
Alistarh, D., Gilbert, S., Guerraoui, R., Travers, C.: How to solve consensus in the smallest window of synchrony. In: Symposium on Distributed Computing (DISC) (2008)
4.
Amir, Y., Coan, B.A., Kirsch, J., Lane, J.: Prime: Byzantine replication under attack. IEEE Trans. Dependable Secure Comput. 8(4), 564–577 (2011)CrossRef
5.
Amoussou-Guenou, Y., Pozzo, A. D., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Correctness of Tendermint-core blockchains. In: Conference on Principles of Distributed Systems (OPODIS) (2018)
6.
Amoussou-Guenou, Y., Pozzo, A. D., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Dissecting tendermint. In: Conference on Networked Systems (NETYS) (2019)
7.
Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., Caro, A.D., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., Muralidharan, S., Murthy, C., Nguyen, B., Sethi, M., Singh, G., Smith, K., Sorniotti, A., Stathakopoulou, C., Vukolic, M., Cocco, S. W., Yellick, J.: Hyperledger fabric: a distributed operating system for permissioned blockchains. In: European Conference on Computer Systems (EuroSys) (2018)
8.
9.
Bazzi, R. A., Ding, Y.: Non-skipping timestamps for Byzantine data storage systems. In: Symposium on Distributed Computing (DISC) (2004)
10.
Biely, M., Widder, J., Charron-Bost, B., Gaillard, A., Hutle, M., Schiper,A.: Tolerating corrupted communication. In: Symposium on Principles of Distributed Computing (PODC) (2007)
11.
12.
13.
Bravo, M., Chockler, G., Gotsman, A.: Liveness and latency of Byzantine state-machine replication. In: Symposium on Distributed Computing (DISC) (2022)
14.
15.
16.
Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: International Cryptology Conference (CRYPTO) (2001)
17.
Cachin,C., Vukolic, M.: Blockchain consensus protocols in the wild (keynote talk). In: Symposium on Distributed Computing (DISC) (2017)
18.
Castro, M.: Practical Byzantine fault tolerance. PhD thesis, Massachusetts Institute of Technology (2001)
19.
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Symposium on Operating Systems Design and Implementation (OSDI) (1999)
20.
21.
22.
Charron-Bost, B., Schiper, A.: The heard-of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49–71 (2009)CrossRefMATH
23.
Crain, T., Gramoli, V., Larrea, M., Raynal, M.: DBFT: efficient leaderless Byzantine consensus and its application to blockchains. In: Symposium on Network Computing and Applications (NCA) (2018)
24.
Dolev, D., Halpern, J.Y., Simons, B., Strong, R.: Dynamic fault-tolerant clock synchronization. J. ACM 42(1), 143–185 (1995)CrossRefMATH
25.
Dragoi, C., Widder, J., Zufferey, D.: Programming at the edge of synchrony. Proc. ACM Program. Lang. 4(OOPSLA), 213:1-213:30 (2020)CrossRef
26.
Dutta, P., Guerraoui, R., Lamport, L.: How fast can eventual synchrony lead to consensus? In: Conference on Dependable Systems and Networks (DSN) (2005)
27.
Dwork, C., Lynch, N.A., Stockmeyer, L.J.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)MathSciNetCrossRef
28.
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH
29.
Gafni, E.: Round-by-round fault detectors: unifying synchrony and asynchrony. In: Symposium on Principles of Distributed Computing (PODC) (1998)
30.
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling Byzantine agreements for cryptocurrencies. In: Symposium on Operating Systems Principles (SOSP) (2017)
31.
Golan-Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M.K., Seredinschi, D., Tamir, O., Tomescu, A.: SBFT: a scalable and decentralized trust infrastructure. In: Conference on Dependable Systems and Networks (DSN) (2019)
32.
Haeberlen, A., Kuznetsov, P.: The fault detection problem. In: Conference on Principles of Distributed Systems (OPODIS) (2009)
33.
Herzberg, A., Kutten, S.: Fast isolation of arbitrary forwarding faults. In: Symposium on Principles of Distributed Computing (PODC) (1989)
34.
Herzberg, A., Kutten, S.: Early detection of message forwarding faults. SIAM J. Comput. 30(4), 1169–1196 (2000)
35.
36.
Keidar, I., Shraer, A.: Timeliness, failure-detectors, and consensus performance. In: Symposium on Principles of Distributed Computing (PODC) (2006)
37.
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)CrossRefMATH
38.
Malkhi, D., Reiter, M.: Unreliable intrusion detection in distributed computations. In: Workshop on Computer Security Foundations (CSFW) (1997)
39.
Milosevic, Z., Biely, M., Schiper, A.: Bounded delay in Byzantine-tolerant state machine replication. In: Symposium on Reliable Distributed Systems (SRDS) (2013)
40.
Mostéfaoui, A., Raynal, M.: Solving consensus using Chandra-Toueg’s unreliable failure detectors: a general quorum-based approach. In: Symposium on Distributed Computing (DISC) (1999)
41.
Naor, O., Baudet, M., Malkhi, D., Spiegelman, A.: Cogsworth: Byzantine view synchronization. In: Cryptoeconomics Systems Conference (CES) (2020)
42.
Naor, O., Keidar, I.: Expected linear round synchronization: the missing link for linear Byzantine SMR. In: Symposium on Distributed Computing (DISC) (2020)
43.
Simons, B., Welch, J., Lynch, N.: An overview of clock synchronization. In: Fault-Tolerant Distributed Computing (1986)
44.
45.
Yin, M., Malkhi, D., Reiter, M. K., Golan-Gueta, G., Abraham, I.: HotStuff: BFT consensus with linearity and responsiveness. In: Symposium on Principles of Distributed Computing (PODC) (2019)
Metadaten
Titel
Making Byzantine consensus live
verfasst von
Manuel Bravo
Gregory Chockler
Alexey Gotsman
Publikationsdatum
02.09.2022
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 6/2022
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-022-00432-y

Weitere Artikel der Ausgabe 6/2022

Distributed Computing 6/2022 Zur Ausgabe

OriginalPaper

Distributed computation with continual population growth

OriginalPaper

Asynchronous reconfiguration with Byzantine failures

OriginalPaper

Linial for lists

EditorialNotes

Special issue on DISC 2020

Premium Partner

    Bildnachweise