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
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Distributed Computing

03.05.2024

Liveness and latency of Byzantine state-machine replication

verfasst von: Manuel Bravo, Gregory Chockler, Alexey Gotsman

Erschienen in: Distributed Computing

Einloggen

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

search-config
loading …

Abstract

Byzantine state-machine replication (SMR) ensures the consistency of replicated state in the presence of malicious replicas and lies at the heart of the modern blockchain technology. Byzantine SMR protocols often guarantee safety under all circumstances and liveness only under synchrony. However, guaranteeing liveness even under this assumption is nontrivial. So far we have lacked systematic ways of incorporating liveness mechanisms into Byzantine SMR protocols, which often led to subtle bugs. To close this gap, we introduce a modular framework to facilitate the design of provably live and efficient Byzantine SMR protocols. Our framework relies on a view abstraction generated by a special SMR synchronizer primitive to drive the agreement on command ordering. We present a simple formal specification of an SMR synchronizer and its bounded-space implementation under partial synchrony. We also apply our specification to prove liveness and analyze the latency of three Byzantine SMR protocols via a uniform methodology. In particular, one of these results yields what we believe is the first rigorous liveness proof for the algorithmic core of the seminal PBFT protocol.

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
Fußnoten
1
In PBFT this information is sent in VIEW-CHANGE messages, which also play a role similar to \( \texttt {WISH}\) messages in our synchronizer (Fig. 3). In PBFT-light we opted to eschew VIEW-CHANGE messages to maintain a clear separation between view synchronization internals and the SMR protocol.
 
2
Recall that even a single \( \texttt {advance}\) call at a correct process may lead to a view switch (§3). For example, with the synchronizer in Fig. 3 this may happen as follows. The \( \texttt {advance}\) call at a process generates \( \texttt {WISH}(v+1)\) (line 2) and the Byzantine processes produce another f copies of the same message. Correct processes receiving the resulting \(f+1\) copies of the message relay it via line 8, which yields \(2f+1\) copies in total. The synchronizer then triggers \(\texttt {new\_view}(v+1)\) notifications at correct processes that receive all these copies (line 15), causing them to enter \(v+1\) without increasing their timeouts.
 
3
The bug was acknowledged by the textbook authors [18].
 
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.-P.: Revisiting fast practical Byzantine fault tolerance (2017). arXiv:​1712.​01367
3.
Abraham, I., Nayak, K., Ren, L., Xiang, Z.: Good-case latency of Byzantine broadcast: a complete categorization. In: Symposium on Principles of Distributed Computing (PODC) (2021)
4.
Aştefănoaei, L., Chambart, P., Del Pozzo, A., Rieutord, T., Tucci-Piergiovanni, S., Zălinescu, E.: Tenderbake-a solution to dynamic repeated consensus for blockchains. In: Symposium on Foundations and Applications of Blockchain (FAB) (2021)
5.
Alistarh, D., Gilbert, S., Guerraoui, R., Travers, C.: Generating fast indulgent algorithms. In: International Conference on Distributed Computing and Networking (ICDCN) (2011)
6.
Amoussou-Guenou, Y., Del Pozzo, A., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Correctness of Tendermint-core blockchains. In: Conference on Principles of Distributed Systems (OPODIS) (2018)
7.
Amoussou-Guenou, Y., Del Pozzo, A., Potop-Butucaru, M., Tucci-Piergiovanni, S.: Dissecting tendermint. In: Conference on Networked Systems (NETYS) (2019)
8.
9.
Bazzi, R.A., Ding, Y.: Non-skipping timestamps for Byzantine data storage systems. In: Symposium on Distributed Computing (DISC) (2004)
10.
Berger, C., Reiser, H.P., Bessani, A.: Making reads in BFT state machine replication fast, linearizable, and live. In: Symposium on Reliable Distributed Systems (SRDS) (2021)
11.
Bessani, A.N., Sousa, J., Adílio Pelinson, R.M., Alchieri, E.: State machine replication for the masses with BFT-SMART. In: Conference on Dependable Systems and Networks (DSN) (2014)
12.
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)
13.
14.
Bravo, M., Chockler, G., Gotsman, A.: Making Byzantine consensus live. In: Symposium on Distributed Computing (DISC) (2020)
15.
16.
Bravo, M., Chockler, G., Gotsman, A.: Making Byzantine consensus live. Distrib. Comput. 35(6), 503–532 (2022)MathSciNetCrossRef
17.
18.
Cachin, C.: Personal communication (2022)
19.
Cachin, C., Guerraoui, R., Rodrigues, L.: Introduction to Reliable and Secure Distributed Programming, 2nd edn. Springer, Berlin (2011)CrossRef
20.
Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: International Cryptology Conference (CRYPTO) (2001)
21.
Cachin, C., Vukolić, M.: Blockchain consensus protocols in the wild (keynote talk). In: Symposium on Distributed Computing (DISC) (2017)
22.
Castro, M.: Practical Byzantine Fault Tolerance. PhD thesis, Massachusetts Institute of Technology (2001)
23.
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Symposium on Operating Systems Design and Implementation (OSDI) (1999)
24.
Castro, M., Liskov, B.: Practical Byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20(4), 398–461 (2002)CrossRef
25.
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)MathSciNetCrossRef
26.
Charron-Bost, B., Schiper, A.: The Heard-Of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49–71 (2009)CrossRef
27.
Civit, P., Dzulfikar, M.A., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J., Vidigueira, M.: Byzantine consensus is \(\theta (n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony! In: Symposium on Distributed Computing (DISC) (2022)
28.
Clement, A., Wong, E., Alvisi, L., Dahlin, M., Marchetti, M.: Making Byzantine fault tolerant systems tolerate Byzantine faults. In: Symposium on Networked Systems Design and Implementation (NSDI) (2009)
29.
30.
Dolev, D., Halpern, J.Y., Simons, B., Strong, R.: Dynamic fault-tolerant clock synchronization. J. ACM 42(1), 143–185 (1995)CrossRef
31.
Doudou, A., Garbinato, B., Guerraoui, R.: Abstractions for devising Byzantine-resilient state machine replication. In: Symposium on Reliable Distributed Systems (SRDS) (2000)
32.
Dragoi, C., Widder, J., Zufferey, D.: Programming at the edge of synchrony. Proc. ACM Program. Lang. 4(OOPSLA), 1–30 (2020)CrossRef
33.
Dwork, C., Lynch, N.A., Stockmeyer, L.J.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)MathSciNetCrossRef
34.
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRef
35.
Freiling, F.C., Guerraoui, R., Kuznetsov, P.: The failure detector abstraction. ACM Comput. Surv. 43(2), 9:1-9:40 (2011)CrossRef
36.
Gafni, E.: Round-by-round fault detectors: unifying synchrony and asynchrony. In: Symposium on Principles of Distributed Computing (PODC) (1998)
37.
Gilbert, S., Guerraoui, R., Kowalski, D.R.: On the message complexity of indulgent consensus. In: Symposium on Distributed Computing (DISC) (2007)
38.
Golan-Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M.K., Seredinschi, Dragos-Adrian, Tamir, Orr, Tomescu, Alin: SBFT: A scalable and decentralized trust infrastructure. In: Conference on Dependable Systems and Networks (DSN) (2019)
39.
Guerraoui, R.: Indulgent algorithms (preliminary version). In: Symposium on Principles of Distributed Computing (PODC) (2000)
40.
Guerraoui, R., Raynal, M.: The information structure of indulgent consensus. IEEE Trans. Comput. 53(4), 453–466 (2004)CrossRef
41.
Haeberlen, A., Kuznetsov, P.: The fault detection problem. In: Conference on Principles of Distributed Systems (OPODIS) (2009)
42.
Herzberg, A., Kutten, S.: Fast isolation of arbitrary forwarding faults. In: Symposium on Principles of Distributed Computing (PODC) (1989)
43.
44.
Keidar, I., Shraer, A.: Timeliness, failure-detectors, and consensus performance. In: Symposium on Principles of Distributed Computing (PODC) (2006)
45.
Kihlstrom, K.P., Moser, L.E., Melliar-Smith, P.M.: Byzantine fault detectors for solving consensus. Comput. J. 46(1), 16–35 (2003)CrossRef
46.
Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: speculative byzantine fault tolerance. ACM Trans. Comput. Syst. 27(4), 7:1-7:39 (2010)
47.
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)CrossRef
48.
Malkhi, D., Reiter, M.: Unreliable intrusion detection in distributed computations. In: Workshop on Computer Security Foundations (CSFW) (1997)
49.
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)
50.
Naor, O., Baudet, M., Malkhi, D., Spiegelman, A.: Cogsworth: Byzantine view synchronization. In: Cryptoeconomics Systems Conference (CES) (2020)
51.
Naor, O., Keidar, I.: Expected linear round synchronization: the missing link for linear Byzantine SMR. In: Symposium on Distributed Computing (DISC) (2020)
52.
Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: Symposium on Distributed Computing (DISC) (2017)
53.
Pass, R., Shi, E.: Thunderella: blockchains with optimistic instant confirmation. In: Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2018)
54.
Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)CrossRef
55.
Simons, B., Welch, J., Lynch, N.: An overview of clock synchronization. In: Fault-Tolerant Distributed Computing (1986)
56.
Sousa, J.: Byzantine State Machine Replication for the Masses. PhD thesis, University of Lisbon (2017)
57.
58.
Veronese, G.S., Correia, M., Bessani, A.N., Lung, L.C.: Spin one’s wheels? Byzantine fault tolerance with a spinning primary. In: Symposium on Reliable Distributed Systems (SRDS) (2009)
59.
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
Liveness and latency of Byzantine state-machine replication
verfasst von
Manuel Bravo
Gregory Chockler
Alexey Gotsman
Publikationsdatum
03.05.2024
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-024-00466-4

Premium Partner

    Bildnachweise