Pith. sign in

REVIEW 4 major objections 5 minor 39 references

From Few to Many Faults: Optimal Adaptive Byzantine Agreement

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper claims that adaptive Byzantine Agreement can simultaneously achieve optimal O(n·f) communication and O(f) rounds in synchronous and partially synchronous networks, and proves that in asynchrony adaptivity is impossible.

desk verdict Important results, but the printed QAB pseudocode contradicts its own message-complexity proof; fixable, not fatal. read the letter →

arxiv 2505.19989 v3 pith:SA76XBMK submitted 2025-05-26 cs.DC

Andrei Constantinescu , Marc Dufay , Anton Paramonov , Roger Wattenhofer This is my paper · ORCID
classification cs.DC MSC 68M1468W15
keywords Byzantineagreementadaptivecommunicationcomplexityrounddispersergraphscommitteeassignmentpartialsynchronyasynchronousconsensusthresholdsignatures
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

The paper claims that Byzantine Agreement can be solved with costs that track the actual number of faults f rather than the worst-case bound t, and that this adaptivity costs nothing in the synchronous and partially synchronous models. Specifically, it exhibits a deterministic protocol (given a PKI) that tolerates t < n/2 faults in synchrony and t < n/3 in partial synchrony, using O(n·f) words and O(f) rounds. In asynchrony, it proves adaptivity is impossible: any protocol with almost-sure termination needs Ω(n+$t^{2}$) expected messages even with no faults, and the paper gives a randomized protocol matching this up to log factors. A sympathetic reader would care because consensus systems rarely experience worst-case numbers of faults, so a design whose cost scales with actual misbehavior could make large networks far more practical.

What carries the argument

The load-bearing object is the bipartite disperser used for committee assignment. For n parties and a parameter f-hat, the graph links each party as a left node to O(log n) committees as right nodes, so that any set of f-hat corrupted parties compromises only O(f-hat log n) committees and blocks at most c_b·f-hat parties (Theorem 3.8). This assignment feeds a Quorum-to-All Broadcast phase in which a small quorum disseminates its decided value to all honest parties through relayers and aggregate signatures, enabling deterministic adaptivity. The other main mechanism is a view-based leader protocol with threshold signatures that stops in O(f) rounds.

What would settle it

Run the committee assignment of Theorem 3.8 on a concrete disperser instance from Theorem 6.2 for, say, n=1000 and f-hat=10; if an adversary can pick 10 parties that block more than c_b·f-hat parties, the theorem and the protocols built on it would fail. Alternatively, an execution of the synchronous protocol in which the retrieval protocol returns ⊥ after f+1 distinct honest leaders would contradict Lemma 10.3 and Theorem 3.1.

Watch

Extended reading notes

Core claim

The central claim is constructive: for synchronous Byzantine Agreement under a PKI and t < n/2, there exists a deterministic algorithm with communication complexity O(n·f) and round complexity O(f), where f ≤ t is the number of actually faulty parties; the same adaptive optimality is achieved in partial synchrony for t < n/3. The paper further claims that in the large-scale regime t = o(n), the dependence on n and t can be decoupled, giving near-optimal O((n log t + t·f)·log n) words and O(f) rounds. The paper also proves a matching lower bound in asynchrony, showing that no adaptive algorithm can beat Ω(n+$t^{2}$) expected messages, so the near-optimal asynchronous protocol is essentially unavoidable.

Load-bearing premise

The optimal complexity claims rely on the existence of a (k,1/2)-bipartite disperser with left degree O(log n) that is currently proven only non-constructively; replacing it with an explicit construction would add polylogarithmic factors to the stated bounds.

Editorial extensions

If this is right

  • For synchronous networks with up to t < n/2 faults, a system can be built that sends O(n·f) messages and finishes in O(f) rounds, matching the lower bounds.
  • For partially synchronous networks, the same adaptive optimality holds for t < n/3.
  • Whenever t = o(n), communication can be decoupled from n, allowing systems to scale to very large n without quadratic cost.
  • In asynchronous networks, every protocol needs Ω(n+t^2) expected messages, so the paper's O((n+t^2) log n) randomized protocol is essentially optimal.
  • The deterministic committee assignment remains secure against an adaptive adversary who chooses which parties to corrupt after seeing the assignment.

Reading between the lines

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

  • If the non-constructive disperser of Theorem 6.2 is ever made explicit with O(log n) degree, the polylogarithmic gaps in Theorems 3.4–3.6 would close exactly; until then, concrete implementations must choose a known explicit disperser and accept the extra polylog factors, as the paper itself notes.
  • The same committee-disperser design could likely be adapted to multi-valued Byzantine Agreement and to state-machine replication, where adaptive communication is currently harder to achieve.
  • A natural testable extension would be to instantiate the exponential-search QAB with an explicit disperser and measure real message counts as a function of f, checking whether the predicted O(n log t + t f) behavior appears at practical scales.
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

4 major / 5 minor

Summary. The paper studies binary Byzantine agreement with security parameter t and actual fault count f. It claims: (i) deterministic synchronous and partially synchronous protocols with optimal resilience (t<n/2 and t<n/3) that communicate O(n f) words and run O(f) rounds; (ii) for t=o(n), protocols with near-optimal O((n log t + t f) log n) communication and O(f) or O(f log n) rounds, using a Quorum-to-All Broadcast primitive based on committees constructed from bipartite dispersers; (iii) a randomized asynchronous protocol with O((n+t^2) log n) expected communication and O(1) expected rounds, together with a lower bound of Omega(n+t^2) for asynchronous agreement with almost-sure termination. The quorum agreement uses a view-based protocol with a retrieval abstraction and a synchronous fallback. The central technical novelty is a deterministic committee assignment with few blocked parties via dispersers, plus a QAB phase that disseminates a value from a quorum of O(t) nodes to all n parties.

Significance. If the proofs are correct, these are strong results: simultaneous O(n f) communication and O(f) rounds with optimal resilience would improve on prior adaptive protocols that require Omega(n) rounds, and the asynchronous lower bound would be the first Omega(t^2) bound in that setting. The paper contains extensive appendix proofs, a modular composition theorem, and clear high-level explanations, and the deterministic results for t=Theta(n) do not depend on the non-constructive disperser, so that part is a solid contribution on its own. However, several load-bearing parts need repair: a pseudocode inconsistency in the QAB phase, an incomplete committee-assignment proof for large f_hat, an incorrect probabilistic step in the asynchronous lower bound, and the non-constructive disperser makes the large-scale 'deterministic' claims conditional.

major comments (4)
  1. [Section 8, QABQuorum pseudocode] The pseudocode for QABQuorum never sends DISPERSE upon StartQuorum: the only Send(DISPERSE) statement is inside the handler for valid COMPLETED messages (lines 11-13). This contradicts the intended behavior described in Section 5.2 and makes Lemmas 8.3, 8.5 and 8.8 inapplicable, since those lemmas count one quorum-to-relayer message per quorum node per relayer. Moreover, if the missing initial send is added while keeping the printed handler, each COMPLETED message triggers a full loop over all O(f_hat log n) relayers, so a phase can cost Theta(f_hat^2 log^2 n) quorum-to-relayer messages rather than O((n + t f_hat) log n). This gap propagates to Theorems 10.6 and 3.4. The prose in Section 5.2 describes a once-only broadcast to all relayers upon StartQuorum, so a local repair is possible, but the formal pseudocode and the complexity proof are inconsistent as written.
  2. [Section 6, Theorem 3.8 proof] The proof applies Theorem 6.2 with |R| = M = 4 c_d f_hat log n, but Theorem 6.2 is stated only for m <= n. When f_hat >= n/(4 c_d log n), which can occur in StartQuorumSync and StartQuorumAsync when f_hat is near t, the cited disperser does not exist under the stated hypothesis, so the committee-assignment theorem is not proved for the full parameter range used by the algorithms. The statement itself can likely be salvaged: for f_hat log n >= n, the trivial assignment of one committee per party satisfies the three listed properties and blocks no honest party. The proof should either split into this case or cite a disperser construction valid for m up to O(n log n).
  3. [Appendix A, proof of Theorem 3.3] The probabilistic step in the lower-bound proof is incorrect. The event cap_{p in C} E_p implies that the total number of messages from B to C is at most |C|*(t/2) = t^2/4, so it is not a subset of {M >= t^2/2}; and from P(M < t^2/2) >= 1/2, the correct complement gives P(union_p E_p^c) >= 1/2, not P(union_p E_p) >= 1/2. The subsequent union-bound conclusion that some p has P(E_p) >= 1/t therefore does not follow. A repair is available: if E[M] < t^2/4, then by averaging some p has E[X_p] < t/2, and Markov gives P(X_p < t/2) > 0, which combined with the later T argument still yields the contradiction. Since this step supports the claimed first Omega(t^2) asynchronous lower bound, it must be rewritten.
  4. [Section 6 and Theorems 3.4-3.6] The stated 'deterministic algorithm' results depend on a bipartite disperser whose existence is only proved non-constructively (Theorem 6.2). The paper acknowledges in Section 6 that switching to the explicit construction of Theorem 6.3 adds polylogarithmic factors, but the abstract and theorem statements still present O((n log t + t f) log n) and O((n+t^2) log n) as achieved by deterministic algorithms. As written, these protocols are not fully explicit, and the claimed optimality is conditional on an unproven explicit disperser with the parameters of Theorem 6.2. The theorems should either be rephrased as existential or conditional results, or the polylogarithmic penalty for explicit constructions should be stated in the main claims.
minor comments (5)
  1. [Section 5.3, Theorem 5.1] The parameter of Messages_BA is inconsistent: the assumption says Messages_BA(n,f) but the conclusion and proof use Messages_BA(t,f); since the quorum has 3t+1 parties, the intended expression is Messages_BA(3t+1, f).
  2. [Section 7, ViewLeaderProtocol pseudocode] The message type 'ReqestSuggestion' is a typo for 'RequestSuggestion', and 'CallQABInitiate()' in DecoupledBA should be 'Run QABInitiate()' for terminology consistency.
  3. [Section 11.2, Lemma 11.4 proof] The sentence 'spO(t log n * f)' should read 'so O(t log n * f)', and the final sentence 'we get the expected round complexity' should read 'message complexity'.
  4. [Section 6, Definition 3.7] Definition 3.7 is printed twice, once in Section 3 and again in Section 6; remove the duplicate.
  5. [Appendix B.4, Theorem B.15] The proof of the Momose-Ren fallback complexity asserts without a formal specification that the graded Byzantine agreement step runs in exactly 4 rounds and that the communication pattern is fixed up to one multicast; since this theorem is load-bearing for Theorem 3.1's fallback case, a self-contained argument or a precise reference to the relevant lemma would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the protocol theorems are built from external building blocks and independent lower bounds; the only suspicious spot is a pseudocode/complexity inconsistency, not a circular reduction.

full rationale

The derivation chain is not circular. The main theorems are proved by composing external black boxes (Cachin et al. asynchronous BA, Spiegelman/HotStuff-style view synchronization, Momose-Ren fallback BA) with a committee assignment derived from standard bipartite disperser existence theorems. Neither the disperser theorems nor the lower bounds used for optimality are from the present authors, and the proofs use the disperser property directly rather than assuming the complexity being proven. The adaptive message bounds are obtained by summing geometric phase costs, and the claimed optimality is compared against independently published lower bounds (Dolev-Reischuk, Spiegelman, Dolev-Strong), not against a value fitted inside the paper. The non-constructive disperser caveat is honestly stated and does not create circularity. The QABQuorum pseudocode in Section 8 appears inconsistent with Lemma 8.3's one-message-per-relayer counting: the printed handler re-broadcasts DISPERSE on each COMPLETED and lacks an initial send, which would break the O(t·f_hat·log n) bound. However, that is an internal correctness/complexity gap, not a circular reduction of a result to its own inputs; it does not make any theorem equivalent by construction to an input or to a self-citation. No load-bearing self-citation exists: none of the cited prior results are by the present authors, so the circularity score is 0.

Assumptions & free parameters 4 free parameters · 6 assumptions · 2 invented entities

The central claims rest on standard cryptographic and network assumptions plus non-constructive disperser existence. The paper's novel protocol parameters are chosen analytically, not fitted to data. No new physical entities are introduced; the invented entities are protocol abstractions with proofs of correctness.

free parameters (4)
  • threshold k = ceil((n+t+1)/2)
    Signature threshold chosen to guarantee any two quorums intersect in at least one honest party. It is an analytical design choice, not fitted to data.
  • phase parameter f_hat = powers of 2 up to t
    Exponential search estimate of the actual fault count f. This is a protocol parameter selected by the algorithm, not fitted to data.
  • view duration = 11 Delta
    Protocol constant long enough for four message phases plus slack. Chosen for proof convenience, not fitted.
  • disperser constant c_b = 4 c_k c_d
    Constant from Theorem 3.8 bounding the number of blocked parties. It is derived from disperser parameters, not data-fitted.
assumptions (6)
  • standard math Existence of (k,1/2)-bipartite dispersers with left degree O(log n) (Theorem 6.2)
    Used to construct committees in Theorem 3.8. The existence is proven non-constructively via the probabilistic method.
  • domain assumption Public-key infrastructure, threshold signatures, and aggregate signatures are available and unforgeable
    All protocols rely on PKI and signature schemes for proofs and aggregation.
  • domain assumption Network models: synchronous known Delta, partial synchrony with unknown GST, asynchronous with eventual delivery
    Standard distributed computing models assumed throughout the paper.
  • domain assumption View synchronization eventually holds after GST: honest nodes stay in a view with an honest leader for long enough
    The view-based agreement protocol requires this to terminate. The paper cites Fever [29] or perfect clocks as implementations.
  • ad hoc to paper The retrieval protocol succeeds at least once among f+1 honest leaders
    Property 5 in Definition 7.1. It is proven for the specific retrieval protocols in Theorems 10.4 and 11.1, but assumed as a general interface for the view-based protocol.
  • ad hoc to paper Momose-Ren fallback protocol has O(n) round and O(n^2) message complexity even with partial participation
    Used as a black box in the synchronous fallback. The paper provides a proof sketch in Theorem B.15.
invented entities (2)
  • Quorum-to-All Broadcast (QAB) primitive
    purpose: Disseminate a value from a quorum to all parties with bounded communication
    Internal protocol abstraction with correctness proofs in the paper, but no external falsifiable handle.
  • Committee-relayer structure with blocked parties
    purpose: Support efficient value dissemination via disperser-based assignment
    Internal construction used to limit message complexity; no external evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of From Few to Many Faults: Optimal Adaptive Byzantine Agreement." pith.science (2026). https://pith.science/paper/SA76XBMK

@misc{pith2026250519989,
  author       = {Pith},
  title        = {Pith review of: From Few to Many Faults: Optimal Adaptive Byzantine Agreement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SA76XBMK}},
  note         = {Machine review of arXiv:2505.19989}
}
abstract

Achieving agreement among distributed parties is a fundamental task in modern systems, underpinning applications such as consensus in blockchains, coordination in cloud infrastructure, and fault tolerance in critical services. However, this task can be intensive, often requiring a large number of messages to be exchanged as well as many rounds of communication, especially in the presence of Byzantine faults. This makes efficiency a central challenge in the design of practical agreement protocols. In this paper, we study the problem of Binary Agreement and give protocols that are simultaneously optimal in both message and round complexity, parameterized by the actual number of Byzantine faults. In contrast to previous works, we demonstrate that optimal message complexity can be achieved without sacrificing latency. Concretely, for a system of $n$ parties tolerating up to $t$ Byzantine faults, out of which only $f \leq t$ are actually faulty, we give the following results: When $t = \Omega(n)$, in the synchronous (resp. partially synchronous) setting, with optimal resiliency $t < n/2$ (resp. $t < n/3$), we describe a deterministic protocol with optimal communication complexity $O(n \cdot (f+1))$ and optimal round complexity $O(f + 1)$. Building upon this previous result, when $t = o(n)$, for both the synchronous and partially synchronous setting, we describe a deterministic protocol with near-optimal communication complexity $\widetilde{O}(n + t\cdot f)$ and near-optimal round complexity $\widetilde{O}(f+1)$. Our approach relies on a novel use of dispersers to efficiently disseminate a value. For the asynchronous setting, we show a $\Omega(n + t^2)$ lower bound in expectation and provide a randomized protocol with near-optimal $\widetilde{O}(n + t^2)$ communication complexity and $O(1)$ round complexity in expectation.

Figures

Figures reproduced from arXiv: 2505.19989 by the authors.

Figure 1
Figure 1. The communication graph for communications with relayers. Nodes are assigned three roles (non [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Evolution of a single view in our partially synchronous Byzantine Agreement protocol, assuming an [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 30 canonical work pages

  1. [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. 2019. Communi- cation Complexity of Byzantine Agreement, Revisited, See [33], 317–326. https://doi.org/10.1145/3293611.3331629

    arXiv 2019

  2. [2]

    Avalanche. 2025. Avalanche Validators Dashboard. https://subnets.avax.network/validators/dashboard/ Accessed: 2025-05-16

    work page 2025

  3. [3]

    Leemon Baird, Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang

    work page

  4. [4]

    Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak, and Sravya Yandamuri. 2025. Leader election with poly-logarithmic communication per party. InAnnual International Cryptology Conference. Springer, 37–68

    work page 2025

  5. [5]

    Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. 2020. Asynchronous Byzantine Agreement with Subquadratic Communication. InTCC 2020, Part I (LNCS, Vol. 12550), Rafael Pass and Krzysztof Pietrzak (Eds.). Springer, Cham, 353–380. https://doi.org/10.1007/978-3-030-64375-1_13

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

  6. [6]

    Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. 2003. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. InEUROCRYPT 2003 (LNCS, Vol. 2656), Eli Biham (Ed.). Springer, Berlin, Heidelberg, 416–432. https://doi.org/10.1007/3-540-39200-9_26

    work page doi:10.1007/3-540-39200-9_26 2003

  7. [7]

    Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short Signatures from the Weil Pairing.Journal of Cryptology17, 4 (Sept. 2004), 297–319. https://doi.org/10.1007/s00145-004-0314-9

    doi:10.1007/s00145-004-0314-9 2004

  8. [8]

    Christian Cachin, Klaus Kursawe, and Victor Shoup. 2005. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography.Journal of Cryptology18, 3 (July 2005), 219–246. https://doi.org/10.1007/ s00145-005-0318-0

    work page 2005

Show all 39 references
  1. [9]

    Bogdan Chlebus, Dariusz Rafal Kowalski, and Jan Olkowski. 2023. Deterministic fault-tolerant distributed computing in linear time and communication. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing. 344–354

    2023

  2. [10]

    Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. 2022. Byzantine Consensus isΘ(𝑛 2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!. In36th International Symposium on Distributed Compu...

    2022 doi

  3. [11]

    Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira

  4. [12]

    Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira, and Igor Zablotchi. 2025. Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms...

    2025 doi

  5. [13]

    Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. 2023. Strong byzantine agreement with adaptive word complexity. https://doi.org/10.48550/arXiv.2308.03524

    2023 doi arXiv

  6. [14]

    Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2020. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In34th International Symposium on Distributed Computing (DISC 2020). 25:1–25:17. https://doi.org/10 .4230/LIPIcs.DISC.2020.25

    2020

  7. [15]

    Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2022. Brief Announcement: Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. In41st ACM PODC, Alessia Milani and Philipp Woelfel (Eds.). ACM, 421–423. https://doi.org/10.1145/3519270.3538458

    2022

  8. [16]

    Shir Cohen, Idit Keidar, and Alexander Spiegelman. 2023. Make every word count: adaptive Byzantine agreement with fewer words. In26th International Conference on Principles of Distributed Systems (OPODIS 2022). Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 18–1

    2023

  9. [17]

    Danny Dolev and Rüdiger Reischuk. 1982. Bounds on Information Exchange for Byzantine Agreement. In1st ACM PODC, Robert L. Probert, Michael J. Fischer, and Nicola Santoro (Eds.). ACM, 132–140. https://doi.org/10.1145/800220 .806690

    1982 doi

  10. [18]

    Danny Dolev, Ruediger Reischuk, and H Raymond Strong. 1990. Early stopping in Byzantine agreement.Journal of the ACM (JACM)37, 4 (1990), 720–741

    1990

  11. [19]

    Lynch, and Larry J

    Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1984. Consensus in the Presence of Partial Synchrony (Preliminary Version). In3rd ACM PODC, Robert L. Probert, Nancy A. Lynch, and Nicola Santoro (Eds.). ACM, 103–118. https://doi.org/10.1145/800222.1599406

    1984

  12. [20]

    Fatima Elsheimy, Giorgos Tsimos, and Charalampos Papamanthou. 2024. Deterministic byzantine agreement with adaptive o (n·f) communication. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1120–1146. From Few to Many Faults: Optimal Adapt...

    2024

  13. [21]

    Fatima Elsheimy, Giorgos Tsimos, and Charalampos Papamanthou. 2024. Deterministic Byzantine Agreement with Adaptive𝑂(𝑛·𝑓) Communication. In35th SODA, David P. Woodruff (Ed.). ACM-SIAM, 1120–1146. https://doi.org/ 10.1137/1.9781611977912.43

    2024 doi

  14. [22]

    Ethernodes. 2025. Ethereum Nodes Distribution - Countries. https://ethernodes.org/countries Accessed: 2025-05-16

    2025

  15. [23]

    Cardano Explorer. 2025. Cardano Stake Pool Explorer. https://cexplorer.io/ Accessed: 2025-05-16

    2025

  16. [24]

    Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process.Journal of the ACM (JACM)32, 2 (1985), 374–382. https://doi.org/10.1145/3149.214121

    1985

  17. [25]

    Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang. 2024. hints: Threshold signatures with silent setup. In2024 IEEE symposium on security and privacy (SP). IEEE, 3034–3052

    2024

  18. [26]

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Scalable leader election. InProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. 990–999

    2006

  19. [27]

    Christoph Lenzen and Sahar Sheikholeslami. 2022. A recursive early-stopping phase king protocol. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 60–69

    2022

  20. [28]

    Andrew Lewis-Pye. 2022. Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model.arXiv preprint arXiv:2201.01107(2022)

    2022 arXiv

  21. [29]

    Andrew Lewis-Pye and Ittai Abraham. 2024. Fever: optimal responsive view synchronisation. In27th International Conference on Principles of Distributed Systems (OPODIS 2023). 14:1–14:16. https://doi.org/10.4230/LIPIcs.OPODIS.2023 .14

    2024 doi

  22. [30]

    Andrew Lewis-Pye, Dahlia Malkhi, and Oded Naor. 2023. Optimal Latency and Communication SMR View- Synchronization. https://blog.chain.link/optimal-latency-and-communication-smr-view-synchronization/

    2023

  23. [31]

    Atsuki Momose and Ling Ren. 2021. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021), Seth Gilbert (Ed.), Vol. 209. 32:1–32:16. https: //doi.org/10.4230/LIPIcs.DISC.2021.32

    2021 doi

  24. [32]

    Jaikumar Radhakrishnan and Amnon Ta-Shma. 2000. Bounds for dispersers, extractors, and depth-two superconcen- trators.SIAM Journal on Discrete Mathematics13, 1 (2000), 2–24

    2000

  25. [33]

    2019.38th ACM PODC

    Peter Robinson and Faith Ellen (Eds.). 2019.38th ACM PODC. ACM

    2019

  26. [34]

    Solana. 2025. Solana Validators Explorer. https://solana.com/validators Accessed: 2025-05-16

    2025

  27. [35]

    Alexander Spiegelman. 2021. In Search for an Optimal Authenticated Byzantine Agreement. In35th International Symposium on Distributed Computing (DISC 2021). 38:1–38:19. https://doi.org/10.4230/LIPIcs.DISC.2021.38

    2021 doi

  28. [36]

    Amnon Ta-Shma, Christopher Umans, and David Zuckerman. 2007. Lossless condensers, unbalanced expanders, and extractors.Combinatorica27, 2 (2007), 213–240

    2007

  29. [37]

    Reiter, Guy Golan-Gueta, and Ittai Abraham

    Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness, See [33], 347–356. https://doi.org/10.1145/3293611.3331591 28 Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Watten...

    2019

  30. [2023]

    In2023 IEEE Symposium on Security and Privacy (SP)

    Threshold signatures in the multiverse. In2023 IEEE Symposium on Security and Privacy (SP). IEEE, 1454–1470. https://doi.org/10.1109/SP46215.2023.10179436

    2023

  31. [2024]

    In43rd ACM PODC, Ran Gelles, Dennis Olivetti, and Petr Kuznetsov (Eds.)

    DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication. In43rd ACM PODC, Ran Gelles, Dennis Olivetti, and Petr Kuznetsov (Eds.). ACM, 145–156. https://doi.org/10.1145/3662158.3662792

Pith tools

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