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
Distributed Computing

22-03-2024

Good-case early-stopping latency of synchronous byzantine reliable broadcast: the deterministic case

Authors: Timothé Albouy, Davide Frey, Michel Raynal, François Taïani

Published in: Distributed Computing

Log in

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

search-config
loading …

Abstract

This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct. This time plays a crucial role in the performance of practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a good-case latency below the worst-case bound of \(t+1\) rounds could be obtained. This work answers this open question positively and proposes a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of \(\textsf{max} (2,t+3-c)\) rounds (or equivalently \(\textsf{max} (2,f+t+3-n)\)), where t is the upper bound on the number of Byzantine processes, \(f\le t\) the number of effectively Byzantine processes, and \(c=n-f\) the number of effectively correct processes. The proposed algorithm does not put any constraint on t, and assumes an authenticated setting, in which individual processes can sign the messages they send, and verify the authenticity of the signatures they receive.

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 "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

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
Appendix
Available only for authorised users
Footnotes
1
In this paper, we will tend to conflate the two problems, as the protocols we discuss solve both BB and BRB.
 
2
In addition, these randomized solutions generally assume a weakly adaptive adversary an adversary that cannot erase messages sent “just before” a process becomes Byzantine, where “just before” means in the same round. A notable exception is the solution presented in [33], which tolerates a strongly-adaptive adversary by exploiting time-lock puzzles. By contrast, a deterministic algorithm that tolerates Byzantine processes inherently tolerates a strongly-adaptive adversary, i.e., an adversary which can remove messages “after the fact”.
 
3
f and c are equivalent, as \(c=n-f\). This paper tends to use c as it leads to more compact formulas.
 
4
‘Deterministic’ is used here with the meaning usually accepted in the distributed algorithm community, i.e. to indicate that the local behavior of processes can be modeled by a deterministic input/outpout automaton, where input and output correspond to the sending and receiving of messages and (in the context of synchronous algorithms) to the progress of rounds. This work also assumes, however, a perfect signature scheme. The notion of determinism does not cover the concrete working of this scheme, which, in practice, would generally rely on some source of randomness to provide encryption and signatures.
 
5
More precisely, this expected number of rounds can be broken down into a deterministic number of synchronous rounds followed by an expected number of asynchronous rounds. The exact breakdown depends, in turn, on the choice of shared random coin used in the algorithm.
 
6
Although correct processes can deliver their message in about \(2\times n/(n-t)\) rounds in this optimized algorithm, they must continue to participate in the algorithm for about the same amount of time, leading to an overall execution time of circa \(4\times n/(n-t)\) rounds in good-cases.
 
7
The extra round of communication induced by \({ delivered}_i\) is needed to ensure all correct processes observe the same predicate \(\textsf{WBP} \) as \(p_i\). However, by delivering as soon as the condition of line 8 is true, the algorithm does not ensure that crashed processes benefit from the brb-No-duplicity and brb-Global-delivery properties. These additional guarantees can be provided at the cost of one extra round by postponing the brb-delivery of m by one round from line 9 to line 4.
 
8
Taking into account the worst case latency, the algorithm’s good-case latency can be written as \(\textsf{min} \big (t+1,\textsf{max} (2,\lambda _\textsf{good})\big )\).
 
9
Detailed examples that illustrate the importance of this revealing chain can also be found in Appendix A.3, where we discuss possible optimization to reduce the communication complexity of the algorithm.
 
10
For simplicity, we say that a process p signed m during round r in \({ view}\) to mean that \({ view}\) contains a chain backing m in which p’s signature appears in rth position. Formally, both formulations are equivalent for correct processes, but they are not for Byzantine processes, as they can sign chains whenever they wish or even use the signature of other Byzantine processes.
 
11
For instance, some works limit the communication power of Byzantine nodes using a Proof-of-Work mechanism under the assumption that individual processes can solve cryptographic puzzles at a limited rate [6, 25].
 
12
When \(R_{\textrm{end}} \le t\), Algorithm 2 brb-delivers in round \(R_{\textrm{end}}\), but also executes one extra round of communication (through the \({ delivered}_i\) variable). This extra round leads to a total of at most \(R_{\textrm{end}} +1\) rounds of communication: the first round followed by \(R_{\textrm{end}} \) subsequent rounds.
 
13
The width of a partially order set (or poset) \((S,<_s)\) is the largest antichain of S, i.e. the largest subset \(X\subseteq S\), such that no pair of elements of X can be compared using \(<_s\).
 
Literature
1.
Abraham, I., Chan, T.H., Dolev, D., Nayak, K., Pass, R., Ren, L., Shi, E.: Communication complexity of Byzantine agreement, revisited. In: ACM Symposium on Principles of Distributed Computing (PODC), pages 317–326 (2019)
2.
Abraham, I., Malkhi, D., Nayak, K., Ren, L., Yin, M.: Sync hotStuff: simple and practical synchronous state machine replication. In: IEEE Symposium on Security and Privacy (S &P), pages 106–118 (2020)
3.
Abraham, I., Nayak, K., Ren, L., Xiang, Z.: Good-case latency of Byzantine broadcast: a complete categorization. In: ACM Symposium on Principles of Distributed Computing (PODC), pages 331–341, (2021)
4.
Abraham, I., Nayak, K., Ren, L., Xiang, Z.: Good-case latency of byzantine broadcast: a complete categorization. In: arXiv:​2102.​07240, pages 1–38 (2021)
5.
Albouy, T., Frey, D., Raynal, M., Taïani, F.: Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In: DISC 2022 - 36th International Symposium on Distributed Computing, Augusta, GA, United States, October (2022)
6.
Andrychowicz, M., Dziembowski, S.: Pow-based distributed cryptography with no trusted setup. In: CRYPTO 2015 – 35th Annual Cryptology Conference, pages 379–399. Springer, (2015)
7.
Attiya, H., Welch, J.L.: Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley series on parallel and distributed computing. Wiley, (2004)
8.
Auvolat, Alex, Frey, Davide, Raynal, Michel, Taïani, François: Money transfer made simple: a specification, a generic algorithm and its proof. Bull. EATCS 132, 22–43 (2020)MathSciNet
9.
Auvolat, Alex, Frey, Davide, Raynal, Michel, Taïani, François: Byzantine-tolerant causal broadcast. Theoret. Comput. Sci. 885, 55–68 (2021)MathSciNetCrossRef
10.
Baudet, M., Danezis, G., Sonnino, A.: FastPay: High-performance Byzantine fault tolerant settlement. In: ACM Advances in Financial Technologies, pages 163–177 (2020)
11.
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: International Conference on the Theory and Application of Cryptology and Information Security, pages 514–532. Springer, (2001)
12.
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: 7th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2001), pages 514–532. Springer (2001)
13.
14.
Cachin, Christian, Guerraoui, Rachid, Rodrigues, Luís. E.T.: Introduction to Reliable and Secure Distributed Programming, 2nd edn. Springer, Cham (2011)CrossRef
15.
Chen, Jing, Micali, Silvio: Algorand: a secure and efficient distributed ledger. Theoret. Comput. Sci. 777, 155–183 (2019)MathSciNetCrossRef
16.
Collins, D., Guerraoui, R., Komatovic, J., Kuznetsov, P., Monti, M., Pavlovic, M., Pignolet, Y.-A., Seredinschi, D.-A., Tonkikh, A., Xygkis, A.: Online payments by merely broadcasting messages. In: Dependable Systems and Networks (DSN), pages 26–38. IEEE, (2020)
17.
Dolev, Danny, Reischuk, Ruediger, Raymond Strong, H.: Early stopping in Byzantine agreement. J. ACM 37(4), 720–741 (1990)MathSciNetCrossRef
18.
Dolev, Danny, Raymond Strong, H.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983)MathSciNetCrossRef
19.
Dwork, Cynthia, Lynch, Nancy A., Stockmeyer, Larry J.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)MathSciNetCrossRef
20.
Fitzi, M., Nielsen, J.B.: On the number of synchronous rounds sufficient for authenticated Byzantine agreement. In: International Symposium on Distributed Computing (DISC), Springer LNCS 5805, pages 449–463 (2009)
21.
Frey, D., Guillou, L., Raynal, M., Taïani, F.: Consensus-free ledgers when operations of distinct processes are commutative. In: 16th International Conference on Parallel Computing Technologies (PaCT), Springer LNCS 12942, pages 359–370 (2021)
22.
Guerraoui, R., Knezevic, N., Quéma, V., Vukolic, M.: The next 700 BFT protocols. In: EuroSys, pages 363–376. ACM, (2010)
23.
Guerraoui, R., Kuznetsov, P., Monti, M., Pavlovic, M., Seredinschi, D.-A.: The consensus number of a cryptocurrency. Distrib. Comput. 35(1), 1–15 (2022)
24.
Imbs, Damien, Raynal, Michel: Trading off \(t\)-resilience for efficiency in asynchronous Byzantine reliable broadcast. Parallel Process. Lett. 26(4), 1650017:1-1650017:8 (2016)MathSciNetCrossRef
25.
Katz, J., Miller, A., Shi, E.: Pseudonymous secure computation from time-lock puzzles. IACR Cryptol. ePrint Arch., page 857 (2014)
26.
Lamport, L., Shostak, R.E., Pease, M.C.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef
27.
Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: 40th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 120–130 (1999)
28.
Mostéfaoui, A., Hamouma, M., Raynal, M.: Signature-free asynchronous Byzantine consensus with \(t<n/3\) and \(O(n^2)\) messages. In: ACM Symposium on Principles of Distributed Computing (PODC), pages 2–9. ACM (2014)
29.
Nayak, K., Ren, L., Shi, E., Vaidya, N.H., Xiang, Z.: Improved extension protocols for Byzantine broadcast and agreement. In: International Symposium on Distributed Computing (DISC), volume 179 of LIPIcs, pages 28:1–28:17 (2020)
30.
Pease, M.C., Shostak, R.E., Lamport, Leslie: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)MathSciNetCrossRef
31.
Raynal, M.: Fault-tolerant message-passing distributed systems: an algorithmic approach. Springer, 459 pages, (2018)
32.
33.
Wan, J., Xiao, H., Devadas, S., Shi, E.: Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions. In: 18th Theory of Cryptography Conference (TCC), Springer LNCS 12550, pages 412–456 (2020)
34.
Wan, Jun, Xiao, Hanshen, Shi, Elaine, Devadas, Srinivas: Expected constant round Byzantine broadcast under dishonest majority. In: 18th Theory of Cryptography Conference (TCC), Springer LNCS 12550, pages 381–411, (2020)
Metadata
Title
Good-case early-stopping latency of synchronous byzantine reliable broadcast: the deterministic case
Authors
Timothé Albouy
Davide Frey
Michel Raynal
François Taïani
Publication date
22-03-2024
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-024-00464-6

Premium Partner

    Image Credits