Pith. sign in

REVIEW 2 major objections 5 minor 40 references

Extending Asynchronous Byzantine Agreement with Crusader Agreement

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Multivalued asynchronous Byzantine agreement reduces to one binary agreement instance plus one crusader-agreement instance, at only $\Theta(\ell n+n^2)$ extra bits.

desk verdict Nice reduction idea, but two load-bearing bugs--EXT liveness and CA2 validity--break the central claims as written. read the letter →

arxiv 2502.02320 v3 pith:GBOZLVUL submitted 2025-02-04 cs.DC cs.CRcs.ITmath.IT

Mose Mizrahi Erbes , Roger Wattenhofer This is my paper · ORCID
classification cs.DCcs.CRcs.ITmath.IT
keywords Byzantineagreementcrusaderasynchronousdistributedalgorithmsinformation-theoreticsecuritymultivaluedextensionprotocolserror-correctingcodesalmost-universalhashing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Multivalued Byzantine agreement asks $n$ parties, up to $t

What carries the argument

The load-bearing machinery is the EXT reduction plus two equality-check layers. EXT uses REC, a terminating reconstruction protocol based on asynchronous data dissemination, so that a single binary Byzantine agreement vote chooses between one reconstructed value $v^*$ and $\bot$; REC's totality converts a 1 vote into universal knowledge of $v^*$. CA1 uses an $\varepsilon$-almost-universal keyed hash so pairs of parties can test input equality by comparing one hash per pair. CA2 replaces hashes with $(n,\delta)$-error-correcting code symbols and adds KCA, a perfectly secure $(8/\sigma)$-crusader agreement protocol; KCA limits the number of distinct non-$\bot$ values that any honest party can see, and Lemma 5.6's collision bound keeps symbol coincidences below the threshold that would break weak consistency. The named complexity targets come from choosing $\delta$ so that each encoded symbol has size $\Theta(\ell/n\cdot\min(1,\varepsilon^2)+\max(1,\log(1/\varepsilon)))$.

What would settle it

Give CA2 an $(n,\delta)$-code whose minimum distance is exactly $n-\delta$, so two distinct messages can share $\delta$ encoded symbols, while keeping the advertised symbol size $\Theta(\ell/\delta+\log(n/\delta))$; Lemma 5.6's collision bound then becomes $(n-3t)/2$ instead of $(n-3t-1)/2$, and one can arrange KCA outputs so that honest parties pass the $n-t$ matching test for two different values, violating weak consistency.

Watch

Extended reading notes

Core claim

The central claim is that crusader agreement is the right intermediate primitive for asynchronous Byzantine agreement extension. EXT runs an $\ell$-bit crusader agreement, feeds any non-$\bot$ output through a terminating reconstruction protocol REC (an asynchronous data dissemination variant with totality), and uses a single binary Byzantine agreement vote to decide whether everyone outputs that reconstructed value or the safe fallback $\bot$. The binary input is 1 only after a party terminates REC, so REC's totality guarantees that a 1 vote makes every honest party learn the same value, while a 0 vote makes everyone output $\bot$. Instantiating EXT with CA1 gives a statistically secure extension with $\Theta(\ell n+n^2(\lambda+\log n))$ bits of communication against $t<n/3$; instantiating with CA2 gives a perfectly secure extension with $O(\ell n/\min(1,\varepsilon^2)+n^2\max(1,\log(1/\varepsilon)))$ bits against $t\le n/(3+\varepsilon)$. The perfect protocol achieves this by replacing hash comparisons with error-correcting-code symbol comparisons and adding KCA, a $(8/\sigma)$-crusader agreement preprocessing step adapted from COOL, to bound how many distinct non-$\bot$ values survive.

Load-bearing premise

CA2's perfect security rests on the existence of near-MDS error-correcting codes in which any $\delta$ of the $n$ encoded symbols already determine the message; the paper cites this family but does not prove its existence, and if the true minimum distance is $n-\delta$ rather than $n-\delta+1$, the collision bound that makes the protocol work degrades by one and the strict inequality $t\le n/(3+\varepsilon)$ can fail.

Editorial extensions

If this is right

  • Any terminating binary asynchronous Byzantine agreement protocol can be lifted to $\ell$-bit inputs with one extra crusader agreement call, constant round overhead, $\Theta(n^2)$ extra messages, and $\Theta(\ell n+n^2)$ extra bits.
  • The statistically secure instantiation EXT+CA1 achieves information-theoretic security against $t<n/3$ with $\Theta(\ell n+n^2(\lambda+\log n))$ bits of communication, matching the asymptotic cost of the best cryptographic extension in that regime.
  • The perfectly secure instantiation EXT+CA2 tolerates $t\le n/(3+\varepsilon)$ for any constant $\varepsilon>0$ with $O(\ell n+C_A+n^2)$ bits when $\varepsilon$ is constant, where $C_A$ is the underlying binary BA communication cost; this matches A-COOL's asymptotic overhead while tolerating more faults.
  • Both extensions run the underlying binary Byzantine agreement only once, avoiding the $n$-fold runs or expected leader elections used by earlier perfect extensions.
  • The CA1 and CA2 protocols are themselves new multivalued crusader agreement protocols with constant rounds and $\Theta(n^2)$ messages, so they can be reused as building blocks beyond BA extension.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implicit design lesson of EXT is that weak consistency plus a totality-giving dissemination layer is enough to lift binary agreement to multivalued agreement; graded consensus, 2-crusader agreement, or vector agreement might replace crusader agreement and yield different complexity trade-offs.
  • If the near-MDS code family used by CA2 is validated, the collision-bounding pattern behind CA2 could be transplanted to perfectly secure reliable broadcast and multivalued broadcast extensions, since those primitives keep the more forgiving $n-t$ thresholds in the COOL-style preprocessing step.
  • CA1's communication carries a $\lambda+\log n$ factor from the hash length; explicit hash families with tighter collision bounds, or derandomized keys, might shave that factor without changing the protocol skeleton.
  • A natural stress test is to instantiate CA2 with Reed-Solomon codes (large symbols, standard proofs) versus the cited near-MDS codes; the claimed communication advantage collapses precisely in the symbol-size regime where the near-MDS property is doing the work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes an asynchronous Byzantine agreement extension, EXT, that reduces multivalued BA on ℓ-bit inputs to one instance of binary BA, one instance of multivalued crusader agreement, a constant number of extra rounds, and Θ(ℓn+n²) extra bits of communication. It then presents two new information-theoretic crusader agreement protocols: CA1, statistically secure for t<n/3 using almost-universal hashing, and CA2, perfectly secure for t≤n/(3+ε) using error-correcting codes and a COOL-inspired preprocessing step. The claimed outcome is the first information-theoretic asynchronous BA extension with quadratic-in-n overhead at resilience t≥n/5, with communication complexity competitive with or better than existing extensions.

Significance. If the central claims were correct, this would be a useful contribution: the EXT reduction is conceptually clean, the complexity accounting is explicit, and the two CA protocols are presented as independently interesting primitives. The comparison table and discussion of prior work are informative. However, the main liveness theorem is not established as written because of a concrete flaw in the REC subprotocol, and the CA2 collision bound relies on an unproved property of the cited codes. These are load-bearing issues for the main theorems, though both appear potentially repairable. The paper does not provide machine-checked proofs or code; the assessment is based on the written proof structure.

major comments (2)
  1. [§3, Appendix A] Theorem 3.3 fails as written because REC totality does not cover parties that never input to REC. In EXT, an honest party that outputs ⊥ from ΠCA (lines 7-9) never inputs to REC. In REC, line 9 stores an incoming MINE symbol only 'if y_i ≠ ⊥'; a party that never acquired an input keeps y_i=⊥, so it never stores any symbol, never reaches line 16, and can never satisfy the termination condition on lines 19-20. Thus, in an execution where CA returns v* to some honest parties and ⊥ to others, and ΠBA outputs 1, the ⊥ parties reach EXT line 17 with y_i=⊥ and never terminate. Such an execution is permitted: CA weak consistency allows mixed v*/⊥ outputs, and binary BA consistency permits output 1 when some honest parties input 0 and some input 1. The proof of Theorem A.2 likewise overclaims that every honest party terminates after t+1 honest parties send YOURS messages; the line-9 guard blocks exactly the parties without REC inputs. Changing the guard to store a symbol when z_j=⊥ would be a natural repair, but as written the liveness proof is unsound.
  2. [§5.3, Lemma 5.6; §2] Lemma 5.6 depends on the assertion that distinct messages share at most δ−1 encoded symbols, i.e. any δ symbols uniquely determine the message. This property is not established for the (n,δ)-codes from [25,30,38]; near-MDS codes in the standard sense have minimum distance n−δ rather than n−δ+1, in which case two codewords can agree in δ positions. Under that weaker property the collision bound becomes ⌊(n−3t)/2⌋ instead of ⌊(n−3t−1)/2⌋, and the strict inequalities in Lemma 5.8 (first bullet) and Lemma 5.9 fail; for n=3t+2, |H|−|E_i| evaluates to t rather than t+1, so the parties outside the core need not multicast ⊥. The parenthetical justification in footnote 3 assumes the decoding guarantee is well-defined for every δ-subset, but that is precisely the MDS-like property that needs proof. The paper should either prove that the cited codes have this property or state it as an explicit assumption and adjust the corresponding claims.
minor comments (5)
  1. [§5.3] The sentence introducing CA2 says 'The protocol CA1 uses the same design as CA1' but should refer to CA2.
  2. [Appendix A, REC pseudocode] In line 4 of REC, the encoding is written as Enc_{n−2t}(v*) but should be Enc_{n−2t}(v_i), since a party encodes its own input.
  3. [§2, Reliable Agreement] The liveness clause contains a typo: 'they they all output' should be 'they all output'.
  4. [§5.3, Complexity of CA2] The word 'csumming' should be 'summing'.
  5. [§4.1, Theorem 4.1] Theorem 4.1 states only validity and consistency for SRA, but the CA1 liveness proof also relies on SRA liveness when all honest parties input the same value to SRA; the liveness argument should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reductions go from black-box primitives and external building blocks to the claimed protocols, and the one self-citation is not load-bearing.

full rationale

The central reduction EXT is a composition of black-box primitives ΠCA, ΠBA and REC, and its proofs invoke only their defining properties; no parameter is fitted to the target result and the communication overhead is obtained by summing complexities of the subprotocols. CA1 is built on a standard almost-universal hash construction and on the paper's own SRA protocol, whose proof uses only quorum intersection and a union bound over hash collisions. CA2 is explicitly adapted from the first two phases of Chen's COOL protocol [10] and uses near-MDS codes from [30]; the graph lemma needed for KCA (Lemma 5.2) is proved in the appendix rather than imported, and the code property underlying Lemma 5.6 is stated as an external assumption, not as the paper's conclusion. The only self-citation ([19]) appears in a related-work enumeration and is not used in any proof. The liveness concern raised about EXT is a soundness question about the use of REC's totality for parties that never input to REC, not a case of the paper's conclusion being equivalent to its inputs; correctness issues of that kind are outside the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard primitives from prior literature: near-MDS codes, almost-universal hashing, ADD, and terminating reliable agreement. No fitted parameters; λ and ε are user-chosen security and resilience trade-offs. No invented entities are introduced.

assumptions (4)
  • domain assumption Near-MDS error correcting codes exist with alphabet size a = Θ(ℓ/k + log(n/k)) for any k.
    Cited [30], used in complexity claims for CA2 (Section 5) and for symbol size bounds.
  • domain assumption The (n, δ)-code has the property that distinct messages share at most δ-1 symbols, i.e., any δ symbols determine the message.
    Stated in Section 5.3 and used for Lemma 5.6 and CA2's collision bound. Not proved in this paper.
  • domain assumption A Θ(2^{-λ}/n²)-almost universal keyed hash function exists with key length κ = ⌈λ+log₂(ℓn²)+1⌉.
    Based on polynomial hashing over GF(2^κ), cited to [8,22], used in CA1 and SRA (Section 4, Appendix B).
  • domain assumption Any binary BA protocol can be augmented with termination and totality at O(n²) communication via a terminating reliable agreement protocol.
    Used in EXT (Section 3), cited to [17].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Extending Asynchronous Byzantine Agreement with Crusader Agreement." pith.science (2026). https://pith.science/paper/GBOZLVUL

@misc{pith2026250202320,
  author       = {Pith},
  title        = {Pith review of: Extending Asynchronous Byzantine Agreement with Crusader Agreement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GBOZLVUL}},
  note         = {Machine review of arXiv:2502.02320}
}
abstract

In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on $\ell$-bit inputs and $\Theta(\ell n + n^2)$ bits of additional communication. As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-\lambda}$ against $t < \frac{n}{3}$ faults with $\Theta(\ell n + n^2(\lambda + \log n))$ bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any $\varepsilon > 0$ be set to tolerate $t \leq \frac{n}{3 + \varepsilon}$ faults with $\mathcal{O}\bigl(\frac{\ell n}{\min(1, \varepsilon^2)} + n^2\max\bigl(1, \log \frac{1}{\varepsilon}\bigr) \bigr)$ bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and information-theoretic security.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 17 canonical work pages

  1. [30]

    2025.Improved Explicit Near-Optimal Codes in the High-Noise Regimes

    Xin Li and Songtao Mao. 2025.Improved Explicit Near-Optimal Codes in the High-Noise Regimes. 5560–5581. doi:10.1137/ 1.9781611978322.190

    work page 2025

  2. [1]

    Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi

    Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2022. Communica- tion complexity of byzantine agreement, revisited.Distrib. Comput. 36, 1 (7 2022), 3–28. doi:10.1007/s00446-022-00428-8

    work page doi:10.1007/s00446-022-00428-8 2022

  3. [2]

    Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. 2022. Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Salerno, Italy) (PODC ’22). Association for Computing Machinery, New York, N...

    arXiv 2022

  4. [3]

    Michael Ben-Or, Ran Canetti, and Oded Goldreich. 1993. Asynchronous secure computation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (San Diego, California, USA) (STOC ’93). Association for Computing Machinery, New York, NY, USA, 52–61. doi:10.1145/167088.167109

    arXiv 1993

  5. [4]

    Garay, and Kenneth J

    Piotr Berman, Juan A. Garay, and Kenneth J. Perry. 1992. Bit Optimal Distributed Consensus . Springer US, Boston, MA, 313–321. doi:10.1007/978-1-4615-3422-8_27

    doi:10.1007/978-1-4615-3422-8_27 1992

  6. [5]

    Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, and Kartik Nayak. 2023. Efficient Adaptively-Secure Byzantine Agreement for Long Messages. In Advances in Cryptology – ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5–9, 2022, Proceedings, Part I (Taipei, Taiwan). S...

    doi:10.1007/978-3-031-22963-3_17 2023

  7. [6]

    Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. 2020. Asynchronous Byzantine Agreement with Sub- quadratic Communication. In Theory of Cryptography, Rafael Pass and Krzysztof Pietrzak (Eds.). Springer International Publishing, Cham, 353–380. doi:10.1007/978-3-030-64375-1_13

    doi:10.1007/978-3-030-64375-1_13 2020

  8. [7]

    Gabriel Bracha. 1987. Asynchronous Byzantine agreement protocols. Information and Computation 75, 2 (1987), 130–143. doi:10.1016/0890-5401(87)90054-X

    doi:10.1016/0890-5401(87)90054-x 1987

Show all 40 references
  1. [8]

    Lawrence Carter and Mark N

    J. Lawrence Carter and Mark N. Wegman. 1979. Universal classes of hash functions. J. Comput. System Sci. 18, 2 (1979), 143–154. doi:10.1016/0022-0000(79)90044-8

    1979 doi

  2. [9]

    Jinyuan Chen. 2020. Fundamental Limits of Byzantine Agreement. arXiv:2009.10965 [cs.IT]

    2020 arXiv

  3. [10]

    Jinyuan Chen. 2021. Optimal Error-Free Multi-Valued Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209) , Seth Gilbert (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Info...

    2021 doi

  4. [11]

    Jinyuan Chen. 2024. OciorCOOL: Faster Byzantine Agreement and Reliable Broadcast. arXiv:2409.06008 [cs.DC]

    2024 arXiv

  5. [12]

    Jinyuan Chen. 2024. OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA. arXiv:2501.00214 [cs.CR]

    2024 arXiv

  6. [13]

    Jinyuan Chen. 2025. OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement. arXiv:2501.11788 [cs.DC]

    2025 arXiv

  7. [14]

    Annick Chopard, Martin Hirt, and Chen-Da Liu-Zhang. 2021. On Communication-Efficient Asynchronous MPC with Adaptive Security. In Theory of Cryptography: 19th International Conference (Raleigh, NC, USA) (TCC ’21) . Springer-Verlag, Berlin, Heidelberg, 35–65. doi:10.1007/978-3-0...

    2021 doi

  8. [15]

    Shir Cohen and Idit Keidar. 2023. Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP. In 37th International Symposium on Distributed Computing (DISC 2023) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 281), Rotem Oshman (Ed.). ...

    2023 doi

  9. [16]

    Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2020. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing (DISC 2020) (Leibniz International 18 Mose Mizrahi Erbes and Roger Wattenhofer Proceedings i...

    2020 doi

  10. [17]

    Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, and Victor Shoup. 2024. Asynchronous Consensus without Trusted Setup or Public-Key Cryptography. InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security (Salt Lake City, UT, USA) (C...

    2024

  11. [18]

    Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous Data Dissemination and its Applications. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (Virtual Event, Republic of Korea) (CCS ’21). Association for Computing Machinery, New Y...

    2021

  12. [19]

    Giovanni Deligios and Mose Mizrahi Erbes. 2024. Closing the Efficiency Gap Between Synchronous and Network- Agnostic Consensus. In Advances in Cryptology – EUROCRYPT 2024 , Marc Joye and Gregor Leander (Eds.). Springer Nature Switzerland, Cham, 432–461. doi:10.1007/978-3-031-5...

    2024 doi

  13. [20]

    Danny Dolev. 1982. The Byzantine generals strike again. Journal of Algorithms 3, 1 (1982), 14–30. doi:10.1016/0196- 6774(82)90004-9

    1982 doi

  14. [21]

    Danny Dolev and Rüdiger Reischuk. 1985. Bounds on information exchange for Byzantine agreement. J. ACM 32, 1 (Jan. 1985), 191–204. doi:10.1145/2455.214112

    1985

  15. [22]

    Matthias Fitzi and Martin Hirt. 2006. Optimally efficient multi-valued byzantine agreement. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (Denver, Colorado, USA) (PODC ’06). Association for Computing Machinery, New York, NY, USA...

    2006

  16. [23]

    Chaya Ganesh and Arpita Patra. 2016. Broadcast Extensions with Optimal Communication and Round Complexity. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Chicago, Illinois, USA) (PODC ’16). Association for Computing Machinery, New York, NY, US...

    2016

  17. [24]

    Chaya Ganesh and Arpita Patra. 2021. Optimal extension protocols for byzantine broadcast and agreement. Distrib. Comput. 34, 1 (Feb. 2021), 59–77. doi:10.1007/s00446-020-00384-1

    2021 doi

  18. [25]

    Guruswami and P

    V. Guruswami and P. Indyk. 2005. Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory 51, 10 (2005), 3393–3400. doi:10.1109/TIT.2005.855587

    2005

  19. [26]

    Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani

    Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani. 2010. Fast asynchronous Byzantine agreement and leader election with full information. ACM Trans. Algorithms 6, 4, Article 68 (Sept. 2010), 28 pages. doi:10.1145/1824777.1824788

    2010

  20. [27]

    Jovan Komatovic, Joachim Neu, and Tim Roughgarden. 2024. Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience. Cryptology ePrint Archive, Paper 2024/1682. https://eprint .iacr.org/2024/1682

    2024

  21. [28]

    Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382–401. doi:10.1145/357172.357176

    1982

  22. [29]

    Fan Li and Jinyuan Chen. 2021. Communication-Efficient Signature-Free Asynchronous Byzantine Agreement. In 2021 IEEE International Symposium on Information Theory (ISIT) (Melbourne, Australia). IEEE Press, 2864–2869. doi:10.1109/ISIT45174.2021.9518010

    2021

  23. [31]

    Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. 2015. Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time. J. ACM 62, 4, Article 31 (Sept. 2015), 21 pages. doi:10.1145/2785953

    2015 doi

  24. [32]

    Achour Mostéfaoui and Michel Raynal. 2010. Signature-Free Broadcast-Based Intrusion Tolerance: Never Decide a Byzantine Value. In Principles of Distributed Systems , Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 14...

    2010 doi

  25. [33]

    Achour Mostéfaoui and Michel Raynal. 2017. Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with $$t<n/3$$, $$O(nˆ2)$$messages, and constant time. Acta Informatica 54, 5 (Aug. 2017), 501–520. doi:10.1007/s00236-016-0269-y

    2017 doi

  26. [34]

    Vaidya, and Zhuolun Xiang

    Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. 2020. Improved Extension Protocols for Byzantine Broadcast and Agreement. In 34th International Symposium on Distributed Computing (DISC 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vo...

    2020 doi

  27. [35]

    Arpita Patra. 2011. Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity. In Principles of Distributed Systems , Antonio Fernàndez Anta, Giuseppe Lipari, and Matthieu Roy (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 34–49. ...

    2011 doi

  28. [36]

    Pease, R

    M. Pease, R. Shostak, and L. Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27, 2 (April 1980), 228–234. doi:10.1145/322186.322188 Extending Asynchronous Byzantine Agreement with Crusader Agreement 19

    1980

  29. [37]

    I. S. Reed and G. Solomon. 1960. Polynomial Codes Over Certain Finite Fields. J. Soc. Indust. Appl. Math. 8, 2 (1960), 300–304. doi:10.1137/0108018

    1960 doi

  30. [38]

    R. M. Roth and V. Skachek. 2006. Improved Nearly-MDS Expander Codes. IEEE Trans. Inf. Theor. 52, 8 (8 2006), 3650–3661. doi:10.1109/TIT.2006.878232

    2006

  31. [39]

    Sam Toueg. 1984. Randomized Byzantine Agreements. InProceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (Vancouver, British Columbia, Canada) (PODC ’84). Association for Computing Machinery, New York, NY, USA, 163–178. doi:10.1145/800222.806744

    1984

  32. [40]

    correct,

    Russell Turpin and Brian A. Coan. 1984. Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement. Inform. Process. Lett. 18, 2 (1984), 73–76. doi:10.1016/0020-0190(84)90027-9 A The Reconstruction Protocol REC The protocol REC is based on the ADD protocol in [18]...

    1984 doi

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.