Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures

Philipp Schneider

REVIEW 3 major objections 4 minor 17 references

Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper claims that a reusable precomputation of $\Theta(n)$ small witness committees reduces Byzantine broadcast, aggregation, consensus, and common coins to near-constant work per node, without signatures.

desk verdict Interesting committee-based BFT scheme with a load-bearing Phase A deadline bug; fixable in principle, but as written the central construction does not go through. read the letter →

arxiv 2501.05377 v2 pith:Q55SU46Z submitted 2025-01-09 cs.DC

Philipp Schneider This is my paper · ORCID

classification cs.DC MSC 68M1468M1568W1568W20

keywords Byzantinefaulttolerancewitnesscommitteesreliablebroadcastconsensuscommoncoinrandomizedprotocolsnear-constantcommunicationbandwidth-restrictedadversary

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

Distributed protocols that survive Byzantine faults usually make each node pay communication proportional to the network size, or rely on expensive signatures. This paper tries to break that trade-off: it claims randomized, signature-free protocols for reliable broadcast, reliable aggregation, consensus, and common coins where each node does only near-constant—$\tilde{O}(1)$, more precisely polylogarithmic—work, while tolerating a constant fraction of Byzantine nodes. The enabler is a reusable precomputation that builds a system of $\Theta(n)$ small witness committees, each with an honest-majority common core, in $\tilde{O}(n)$ rounds with $\tilde{O}(1)$ per-node bandwidth per round. If the construction is right, the hard assumptions about synchrony and adversary strength are confined to that one precomputation, after which many instances of broadcast and consensus can be solved cheaply and without signatures.

What carries the argument

The load-bearing object is the system of witness committees: for each of $\Theta(n)$ nodes, a near-constant-size set of witnesses with an honest-majority common core, agreed upon by all honest nodes. The paper constructs it in three phases: Phase A uses random sampling so each node joins $O(\log n+\lambda)$ committees, Phase B filters out committees with weak support by running a small deterministic consensus inside each candidate core, and Phase C spreads knowledge of the surviving committees by random sampling requests. The bandwidth restriction on the adversary ($n/24$ of honest bandwidth) is what makes Phase A safe: it caps how many preliminary committees the adversary can flood into invalidity, and the paper proves a constant fraction survive.

What would settle it

Run Phase A on a simulated network of $n$ nodes with an adversary that controls exactly $n/24$ nodes and spends its full per-round bandwidth budget on membership announcements for a chosen set of committees. Lemma 2.8 predicts the adversary can invalidate at most about $5n^2/12$ preliminary committee instances across all honest views; if even one run invalidates more than that under the stated budget, Theorem 6's availability guarantee $\alpha=1/6$ fails. A second check: with the bandwidth cap removed, the same adversary can invalidate all committees, confirming that the cap, not just the node fraction, is load-bearing.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central result is that a Monte Carlo algorithm computes a system of witness committees with availability $\alpha=1/6$ and near-constant committee size $\beta=O(\log n+\lambda)$ in $O(n)$ rounds with $\mathrm{poly}(\log n+\lambda)$ bits per node per round, succeeding with high confidence against a Byzantine adversary that controls at most $n/24$ nodes and $n/24$ of the total bandwidth. The committees satisfy agreement (all honest nodes' local views of a committee share a common core of honest nodes), membership bounds (no node is overloaded, no committee is large), and availability (at least $n/6$ nodes have valid committees). Given such a system, the paper derives a deterministic reliable broadcast that works asynchronously with $O(\delta)$ work per node in $O(\log_\delta n)$ rounds, and synchronous reliable aggregation, common coins, and multi-value consensus with fewer than $n/2$ Byzantine nodes, all without signatures.

Load-bearing premise

The whole result rests on the bandwidth-restricted adversary of Definition 1.2: Byzantine nodes control at most $n/24$ nodes and send at most $n/24$ of the honest per-round bandwidth; if that cap is removed, the Phase A flooding argument in Lemma 2.8 breaks, the committee system is no longer guaranteed, and every downstream protocol collapses.

Editorial extensions

If this is right

For any constant degree $\delta>1$, reliable broadcast runs in $O(\log n)$ rounds with near-constant work per node, deterministically and asynchronously, after the precomputation supplies the committee system.
Reliable aggregation, common coins (with a 1-late adversary), and deterministic consensus with $t<n/2$ Byzantine nodes each run in $O(\log_\delta n)$ rounds with $O(\delta)$ work per node, all without signatures.
Because the committee system carries $\Omega(n)$ bits of Shannon entropy, any algorithm that lets every node learn it needs $\tilde{\Omega}(n)$ rounds or bits, so the precomputation is optimal up to logarithmic factors.
The precomputation cost amortizes: the same committee system can serve many subsequent broadcast, aggregation, and consensus instances, and the execution-phase protocols are deterministic.

Reading between the lines

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

A direct next step would be to optimize the deliberately unoptimized $1/24$ adversary bounds and derive the exact trade-off curve between the adversary's node/bandwidth fraction and the availability and committee-size parameters.
Because the execution layer relies only on the existence of the committee system, the same precomputation could plausibly be reused for blockchain sharding, where each shard is a witness committee and cross-shard communication goes through the broadcast tree; the paper mentions this application without specifying a protocol.
In practice the bandwidth-restricted adversary must be enforced at the network layer, for instance by rate limiting or by guaranteed honest send capacity; without such enforcement, a Byzantine node that can send arbitrary volume would invalidate the Phase A committees and nullify the theorems.

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.

Desk Editor's Note

read the letter

The main idea is genuinely new: instead of relying on one large witness committee or on cryptographic sortition, the paper computes a system of Theta(n) small witness committees by a three-phase randomized sampling procedure, and then uses that system as a reusable precomputation for broadcast, aggregation, consensus, and common coins. If the construction worked, it would be a substantial advance for signature-free BFT with near-constant per-node work. The modular design is also good: the application layer only assumes the existence of the committee system, and the probabilistic analysis in Phases B and C is careful, with explicit Chernoff bounds and w.h.c. guarantees. The paper is also honest about the 1/24 adversary share and says it is not optimized. But there is a serious bug in Phase A. In Algorithm 1, each honest node samples eta committees and sends member messages to all n nodes, so it sends eta n messages, each containing a committee identifier of log n bits. With per-node bandwidth B = poly(log n + lambda) bits per round, an honest sender needs Omega(eta n log n / B) rounds just to transmit its announcements. The deadline in Line 5 is ceil(beta n / B), with beta = Theta(eta), i.e. Theta(eta n / B) rounds, a factor Theta(log n) too short. Lemma 2.3 explicitly asserts that this deadline is sufficient for honest nodes to deliver all membership announcements, and the common-core agreement property follows from that. Without it, the whole Phase A/B/C construction loses its foundation. This is not just a modeling choice; it is an internal correctness gap in the main theorem. The good news is that the bug looks fixable: increase the deadline by a log n factor, which does not change the claimed O-tilde(n) round complexity since the paper suppresses log factors. But as written, the proof of Theorem 6 is incomplete. The other concern the reader raised is also real but less severe: Theorems 5 and 10 advertise consensus with f < n/2 Byzantine nodes, but that is conditional on having a system of witness committees, and the only construction in the paper only supports f <= n/24. The abstract's constant fraction is technically true, but the paper's emphasis on f < n/2 for consensus is misleading without a construction that achieves it. This is an overclaim in presentation, not a logical contradiction. Who is this for? Distributed systems theorists working on scalable BFT, randomized consensus, and committee-based protocols. The paper deserves a serious referee, because the idea is substantive and the central flaw appears to be a correctable constant/log factor mistake rather than a wrong approach. I would not cite it in its current form, but I would want to see a revised version.

Referee Report

3 major / 4 minor

Summary. The paper proposes a signature-free, randomized precomputation step that builds a system of Θ(n) small witness committees with honest-majority cores, and then uses this system deterministically to solve reliable broadcast, reliable aggregation, common coins, and consensus with near-constant per-node work. The main claimed contribution is Theorem 6, a Monte Carlo construction of such committees in O(n) rounds with O(poly(log n + λ)) bandwidth per node per round, tolerating a synchronous adversary controlling at most n/24 nodes and n/24 of the total bandwidth. The execution layer (Algorithms 4-9) is modular and, if Theorem 6 is accepted, the proofs of broadcast, aggregation, and consensus are mostly straightforward applications of the witness-committee structure. The paper supplies detailed Chernoff-bound arguments and a clear separation between the randomized precomputation phase and the deterministic execution phase.

Significance. If the construction can be fixed, the paper would make a substantial contribution: it would show that the expensive part of signature-free BFT can be moved into a reusable randomized precomputation step, after which multiple distributed tasks can be solved with near-constant work per node. The modular structure, the use of a bandwidth-restricted adversary to bound committee corruption, and the attempt to avoid cryptographic assumptions are all valuable and worth publishing. However, the main construction currently contains a load-bearing round-complexity error in Phase A that undermines the common-core guarantee and therefore the entire committee system. The paper also advertises consensus for t < n/2 in Theorem 10 while only proving the committee construction for t ≤ n/24; this conditional claim needs to be scoped precisely. Because the Phase A error appears fixable by a logarithmic factor in the deadline, I recommend major revision rather than rejection.

major comments (3)

[§2.1, Algorithm 1, Line 5; Lemma 2.3] The deadline in Algorithm 1 is too short by a Θ(log n) factor. Each honest node samples η committees and sends ⟨member,u⟩ to all n nodes, so it must transmit η n messages. Each such message contains a committee identifier u, costing Θ(log n) bits. With bandwidth σ bits per round, an honest sender needs Θ(η n log n / σ) rounds to deliver all of its membership announcements. The deadline in Line 5 is τ + ⌈η n / σ⌉, which is a factor Θ(log n) smaller. Consequently, Lemma 2.3's assertion that 'the time bound in Line 5 is sufficient for v to send all its messages' is false as written: honest membership announcements can arrive after the deadline, so honest nodes may build different sets A_{u,v}, and the claimed common core in Definition 2.2 and Lemmas 2.4-2.6 is not established. Since Phases B and C build directly on this common-core agreement, this is a load-bearing error for Theorem 6. The fix is local: multiply the deadline by log n (or equivalently define σ as a per-message bandwidth), and re-check Lemma 2.8 with the longer window; an adversary's extra bit budget over the longer window is offset by the log n bit cost of each membership message, so the bound on invalidated committees should survive.
[§3.6, Theorem 10 and §3.4, Theorem 7 versus §2, Theorem 6] The paper's headline theorems claim consensus and reliable broadcast for t < n/2 Byzantine nodes, but the only committee construction given in Theorem 6 is proved only for t, f ≤ n/24. Theorem 10 is conditional on 'a system of witness committees as in Definition 2.1', and the paper does not prove that such a system exists for t up to n/2; the Phase A/B/C lemmas explicitly require t ≤ n/24 (Lemmas 2.8, 2.14, 2.17, 2.18). This is not circular, but it is an unsupported extension of the advertised resilience threshold. The authors should either state clearly that Theorems 7-10 are conditional on an externally supplied system whose existence for t < n/2 is an open assumption, or restrict the consensus theorem to the t ≤ n/24 regime that the construction actually supports.
[§2.2, Lemma 2.12] The simulation argument for running Garay-Moses in parallel on many small cores is sketched rather than proved: Lemma 2.12 asserts that differing local views C'_{u,v} can be treated as Byzantine behavior in the original protocol, but it does not specify how a node handles messages from participants that are in one local view but not in another, nor how the interleaving of O(η) parallel consensus instances affects the round count when the set of cores is not known identically to all honest nodes. The conclusion is plausible, but the proof should spell out the simulation at the level of message delivery and round schedules, especially because the final round-complexity claim in Theorem 6 depends on this step.

minor comments (4)

[§2.2, Lemma 2.15, proof] The proof states 'the existence of a v ∈ H with C_{u,v} = ∅ implies |Supp(u)| ≥ n/3'; the intended statement is clearly 'C_{u,v} ≠ ∅'. Please correct this typo, as it obscures the contrapositive argument.
[§2.3, Lemma 2.18, proof] In the first bullet of the proof, 'C_u ⊆ C_{u,v}^{(?)}' is written with an unclear superscript; it should be 'C_u ⊆ C_{u,v}' for every honest v. Please clarify the notation.
[§3.6, Theorem 9, proof] The sentence 'There exists at least one honest node (due to witness committees having honest cores)' is imprecise; the existence of an honest node follows from t < n and n ≥ 1, not from the committee structure. Please rephrase.
[§1.2 and §2.1, notation] The variables β, η, ω, and σ are introduced in different places and the paper sometimes conflates 'messages' with 'bits' in informal discussions (e.g., Lemma 2.8's proof counts adversary messages as if each cost one bit). A short table or a consistent statement of message bit-lengths in Phase A would help avoid this confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the witness-committee construction is self-contained and the Section 3 protocols are conditional on that independently constructed system.

full rationale

The derivation chain is self-contained rather than circular. Phase A constructs preliminary committees by random sampling: Lemma 2.5 bounds honest membership with Chernoff bounds, and the adversary bound in Lemma 2.8 is an explicit bandwidth-cap assumption, not a re-packaged conclusion. Phase B uses only support-size arguments and an external Garay-Moses consensus subroutine (Lemma 2.11, cited to [11]), and Phase C samples the Phase B committees to assemble final committees. Theorem 6 then composes these lemmas; the availability alpha = 1/6 comes from Lemma 2.8's counting argument. The Section 3 algorithms (lazy consensus, reliable broadcast, aggregation, consensus, common coin) are conditional theorems "given a system of witness committees", so they do not assume what they prove. The randomized and adversarial requirements are confined to the precomputation phase and are stated as assumptions. The only self-citation, [1] (Amores-Sesar, Cachin, and Schneider), supports the introductory remark that scalable randomized approaches sacrifice resiliency; it is not load-bearing in any lemma or theorem. The paper's own caveat that the 1/24 Byzantine fraction is not fully optimized is a modeling concession, not a circular step. No fitted input is later called a prediction, and no known result is renamed without attribution; the common-core terminology is explicitly credited to the gather protocol [7].

Assumptions & free parameters 5 free parameters · 7 assumptions · 2 invented entities

free_parameters: the 1/24 node and bandwidth bounds are hand-chosen and not optimized, the sampling sizes and tree degree are asymptotic parameters with constants left unspecified, and lambda is a user input. axioms: standard concentration bounds, the Garay-Moses consensus theorem, synchronous network and authenticated links, the static bandwidth-restricted adversary, the 1-late adversary for common coin, and implicitly the unproven existence of honest-majority committees at f < n/2 in Theorem 10. invented_entities: witness committees and the broadcast tree are constructive algorithmic primitives, not physical postulates.

free parameters (5)

Byzantine node fraction bound t/n = 1/24
Chosen by hand in Theorem 6 and Lemma 2.8; the paper says this fraction is not fully optimized and any larger fraction would break the bandwidth-invalidation argument.
Byzantine bandwidth fraction bound = 1/24
Definition 1.2 and Lemma 2.8; the adversary may send at most n times sigma divided by 24 bits per round, needed to prevent Byzantine nodes from invalidating all preliminary committees in Phase A.
Sampling sizes epsilon and eta = Theta(log n + lambda) with unspecified constants
Algorithm parameters in Phases A and C; chosen large enough for Chernoff bounds but constants are not pinned down, so implementations must tune them.
Tree degree delta = user-chosen, at least 1/alpha + 1
Tradeoff parameter between per-node work and round complexity in Theorems 2, 7, 8, 9, and 10.
Security parameter lambda = user-provided
Used in the with-high-confidence definition to ensure negligible failure probability even for small networks; treated as an input, not fitted to data.

assumptions (7)

domain assumption Synchronous network with known round bounds during precomputation.
Invoked by Algorithm 1's fixed deadline for membership announcements and by Theorem 6; Phase B also relies on synchronized rounds for the Garay-Moses subroutines.
domain assumption Reliable private point-to-point links where the receiver can always identify the sender.
Stated in Section 1.1; used in Lemma 2.3 to ensure only a node itself can cause its membership in a committee, and throughout Section 3 for message authentication without signatures.
domain assumption Static Byzantine adversary controlling a fixed set of at most n/24 nodes and at most 1/24 of total honest bandwidth.
Definition 1.2 and Theorem 6; the bandwidth cap is used in Lemma 2.8 to bound the number of Phase A committees the adversary can invalidate.
domain assumption 1-late adversary for the common-coin protocol.
Definition 1.3 and Theorem 9; needed so Byzantine coins are fixed before honest coins are committed, making the XOR of all committed coins random.
standard math Chernoff bounds and union bounds (Appendix A, Lemma A.8, Corollary A.7).
Used to prove with-high-confidence concentration of committee membership in Lemmas 2.5, 2.8, 2.16, and 2.17.
standard math Garay-Moses synchronous consensus solves consensus for t < n/3 Byzantine parties in t+1 rounds (Lemma 2.11, from reference [11]).
Used in Phase B, Lemma 2.13, to agree on validity bits inside small committee cores.
ad hoc to paper A system of witness committees with honest-majority cores exists even when f < n/2.
Theorem 10 and the simplified Theorem 5 state consensus with f < n/2 given such a system, but the paper only constructs committees for f at most n/24; this existence condition is asserted, not derived.

invented entities (2)

System of witness committees independent evidence
purpose: Small honest-majority quorums associated with a constant fraction of nodes, used to run broadcast, aggregation, consensus, and common coins with low per-node work.
Constructive: Algorithms 1-3 and Theorem 6 provide a concrete randomized construction, so the object is not merely postulated; it can be validated by simulation or formal proof.
Broadcast tree over witness committees independent evidence
purpose: A locally computable tree routing reliable broadcast and aggregation between committees with O(log n) round complexity.
Constructive: Lemma 3.8 gives an explicit deterministic procedure from the agreed set of valid committees; again algorithmically checkable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures." pith.science (2026). https://pith.science/paper/Q55SU46Z

@misc{pith2026250105377,
  author       = {Pith},
  title        = {Pith review of: Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q55SU46Z}},
  note         = {Machine review of arXiv:2501.05377}
}

read the original abstract

Numerous distributed tasks have to be handled in a setting where a fraction of nodes behaves Byzantine, that is, deviates arbitrarily from the intended protocol. Resilient, deterministic protocols rely on the detection of majorities to avoid inconsistencies if there is a Byzantine minority, which requires individual nodes to handle a communication workload that is proportional to the size of the network -- an intolerable disadvantage in large networks. Randomized protocols circumvent this by probing only small parts of the network, thus allowing for consistent decisions quickly and with a high level of confidence with communication that is near-constant in the network size. However, such protocols usually come with the drawback of limiting the fault tolerance of the protocol, for instance, by severely restricting the number or type of failures that the protocol can tolerate. We present randomized protocols to reliably aggregate and broadcast information, form consensus and compute common coins that tolerate a constant fraction of Byzantine failures, do not require cryptographic signatures and have a near-constant time and message complexity per node. Our main technique is to compute a system of witness committees as a pre-computation step almost optimally. This pre-computation step allows to solve the aforementioned distributed tasks repeatedly and efficiently, but may have far reaching further applications, e.g., for sharding of distributed data structures.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 6 canonical work pages

[1]

An Analysis of Avalanche Consensus

Ignacio Amores-Sesar, Christian Cachin, and Philipp Schneider. “An Analysis of Avalanche Consensus”. In: Structural Information and Communication Complexity - 31s t Interna- tional Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, Ma y 27-29, 2024, Proceedings . Ed. by Yuval Emek. Vol. 14662. Lecture Notes in Computer Science . Springer, 2024, pp. 27–44. ...

work page doi:10.1007/978-3-031-60603-8 2024
[2]

A Tight Lower Bound for Rando mized Syn- chronous Consensus

Ziv Bar-Joseph and Michael Ben-Or. “A Tight Lower Bound for Rando mized Syn- chronous Consensus”. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, Puerto Vall arta, Mexico, June 28 - July 2, 1998. Ed. by Brian A. Coan and Yehuda Afek. ACM, 1998, pp. 193–199. /u.sc/r.sc/l.sc: https ://doi.org/10.1145...

arXiv 1998
[3]

Dynamic Probabilistic Reliable Broa dcast

João Paulo Bezerra et al. “Dynamic Probabilistic Reliable Broa dcast”. In: 28th Inter- national Conference on Principles of Distributed Systems, OPODIS 2024, December 11- 13, 2024, Lucca, Italy . Ed. by Silvia Bonomi et al. Vol. 324. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 31:1–31:30. /u.sc/r.sc/l.sc: https://doi.org/10.4230 /LIPI...

work page 2024
[4]

The industrial internet of things (IIoT): An anal ysis framework

Hugh Boyes et al. “The industrial internet of things (IIoT): An anal ysis framework”. In: Comput. Ind. 101 (2018), pp. 1–12. /u.sc/r.sc/l.sc: https://doi.org/10.1016/j.compind .2018.04.015

doi:10.1016/j.compind 2018
[5]

An Asynchronous [(n-1)/3]-Resilient Consensus Protocol

Gabriel Bracha. “An Asynchronous [(n-1)/3]-Resilient Consensus Protocol”. In: Pro- ceedings of the Third Annual ACM Symposium on Principles of D istributed Computing, Vancouver, B. C., Canada, August 27-29, 1984 . Ed. by Tiko Kameda et al. ACM, 1984, pp. 154–162. /u.sc/r.sc/l.sc: https://doi.org/10.1145/800222.806743

arXiv 1984
[6]

Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.) Springer, 2011. /i.sc/s.sc/b.sc/n.sc: 978-3-642-15259-7. /u.sc/r.sc/l.sc: https://doi.org/10.1007/978-3-642-15260-3

doi:10.1007/978-3-642-15260-3 2011
[7]

Fast asynchronous Byzantine agreement w ith optimal resilience

Ran Canetti and Tal Rabin. “Fast asynchronous Byzantine agreement w ith optimal resilience”. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on The ory of Computing, May 16-18, 1993, San Diego, CA, USA . Ed. by S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal. ACM, 1993, pp. 42–51. /u.sc/r.sc/l.sc: https://doi.org/10.11 45/167088.167105

arXiv 1993
[8]

Stabilizing consensus with the power of two c hoices

Benjamin Doerr et al. “Stabilizing consensus with the power of two c hoices”. In: SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-locate d with FCRC 2011) . Ed. by Rajmohan Rajaraman and Friedhelm Meyer auf der Heide. ACM, 2011 , pp. 149–158. /u.sc/r.sc/l.sc: htt...

arXiv 2011

Show all 17 references

[9]

Bounds on Information Exchange for Byzantine Agreement

Danny Dolev and Rüdiger Reischuk. “Bounds on Information Exchange for Byzantine Agreement”. In: J. ACM 32.1 (1985), pp. 191–204. /u.sc/r.sc/l.sc: https://doi.org/10.1145 /2455.214112. 43

1985
[10]

Impossib ility of Distributed Consensus with One Faulty Process

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. “Impossib ility of Distributed Consensus with One Faulty Process”. In: J. ACM 32.2 (1985), pp. 374–382. /u.sc/r.sc/l.sc: http s://doi.org/10.1145/3149.214121

1985
[11]

Fully Polynomial Byzantine Agr eement for n > 3t Processors in t + 1 Rounds

Juan A. Garay and Yoram Moses. “Fully Polynomial Byzantine Agr eement for n > 3t Processors in t + 1 Rounds”. In: SIAM J. Comput. 27.1 (1998), pp. 247–290. /u.sc/r.sc/l.sc: https://doi.org/10.1137/S0097539794265232

1998 doi
[12]

Algorand: Scaling Byzantine Agreements for C ryptocurrencies

Yossi Gilad et al. “Algorand: Scaling Byzantine Agreements for C ryptocurrencies”. In: Proceedings of the 26th Symposium on Operating Systems Prin ciples, Shanghai, China, October 28-31, 2017. ACM, 2017, pp. 51–68. /u.sc/r.sc/l.sc: https://doi.org/10.1145/313274 7.3132757

2017 doi
[13]

Signat ure-Free Asyn- chronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Ex- pected Time

Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. “Signat ure-Free Asyn- chronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Ex- pected Time”. In: J. ACM 62.4 (2015), 31:1–31:21. /u.sc/r.sc/l.sc: https://doi.org/10.1145/2 785953

2015 doi
[14]

Reaching Agreement in the Presence of Faults

Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. “Reaching Agreement in the Presence of Faults”. In: J. ACM 27.2 (1980), pp. 228–234. /u.sc/r.sc/l.sc: https://doi.org /10.1145/322186.322188

1980
[15]

B reaking the Ω(√/u1D45B) Bar- rier: Fast Consensus under a Late Adversary

Peter Robinson, Christian Scheideler, and Alexander Setzer. “B reaking the Ω(√/u1D45B) Bar- rier: Fast Consensus under a Late Adversary”. In:Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18,

2018
[16]

Scalable and Probabilistic Leaderless B FT Consensus through Metastability

Team Rocket et al. “Scalable and Probabilistic Leaderless B FT Consensus through Metastability”. In: CoRR abs/1906.08936 (2019). arXiv: 1906.08936. /u.sc/r.sc/l.sc: http://arx iv.org/abs/1906.08936. 44

2019 arXiv
[2018]

by Christian Scheideler and Jeremy T

Ed. by Christian Scheideler and Jeremy T. Fineman. ACM, 2018, pp. 17 3–182. /u.sc/r.sc/l.sc: https://doi.org/10.1145/3210377.3210399

2018

Pith tools

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

[1] [1]

An Analysis of Avalanche Consensus

Ignacio Amores-Sesar, Christian Cachin, and Philipp Schneider. “An Analysis of Avalanche Consensus”. In: Structural Information and Communication Complexity - 31s t Interna- tional Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, Ma y 27-29, 2024, Proceedings . Ed. by Yuval Emek. Vol. 14662. Lecture Notes in Computer Science . Springer, 2024, pp. 27–44. ...

work page doi:10.1007/978-3-031-60603-8 2024

[2] [2]

A Tight Lower Bound for Rando mized Syn- chronous Consensus

Ziv Bar-Joseph and Michael Ben-Or. “A Tight Lower Bound for Rando mized Syn- chronous Consensus”. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, Puerto Vall arta, Mexico, June 28 - July 2, 1998. Ed. by Brian A. Coan and Yehuda Afek. ACM, 1998, pp. 193–199. /u.sc/r.sc/l.sc: https ://doi.org/10.1145...

arXiv 1998

[3] [3]

Dynamic Probabilistic Reliable Broa dcast

João Paulo Bezerra et al. “Dynamic Probabilistic Reliable Broa dcast”. In: 28th Inter- national Conference on Principles of Distributed Systems, OPODIS 2024, December 11- 13, 2024, Lucca, Italy . Ed. by Silvia Bonomi et al. Vol. 324. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 31:1–31:30. /u.sc/r.sc/l.sc: https://doi.org/10.4230 /LIPI...

work page 2024

[4] [4]

The industrial internet of things (IIoT): An anal ysis framework

Hugh Boyes et al. “The industrial internet of things (IIoT): An anal ysis framework”. In: Comput. Ind. 101 (2018), pp. 1–12. /u.sc/r.sc/l.sc: https://doi.org/10.1016/j.compind .2018.04.015

doi:10.1016/j.compind 2018

[5] [5]

An Asynchronous [(n-1)/3]-Resilient Consensus Protocol

Gabriel Bracha. “An Asynchronous [(n-1)/3]-Resilient Consensus Protocol”. In: Pro- ceedings of the Third Annual ACM Symposium on Principles of D istributed Computing, Vancouver, B. C., Canada, August 27-29, 1984 . Ed. by Tiko Kameda et al. ACM, 1984, pp. 154–162. /u.sc/r.sc/l.sc: https://doi.org/10.1145/800222.806743

arXiv 1984

[6] [6]

Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.) Springer, 2011. /i.sc/s.sc/b.sc/n.sc: 978-3-642-15259-7. /u.sc/r.sc/l.sc: https://doi.org/10.1007/978-3-642-15260-3

doi:10.1007/978-3-642-15260-3 2011

[7] [7]

Fast asynchronous Byzantine agreement w ith optimal resilience

Ran Canetti and Tal Rabin. “Fast asynchronous Byzantine agreement w ith optimal resilience”. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on The ory of Computing, May 16-18, 1993, San Diego, CA, USA . Ed. by S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal. ACM, 1993, pp. 42–51. /u.sc/r.sc/l.sc: https://doi.org/10.11 45/167088.167105

arXiv 1993

[8] [8]

Stabilizing consensus with the power of two c hoices

Benjamin Doerr et al. “Stabilizing consensus with the power of two c hoices”. In: SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-locate d with FCRC 2011) . Ed. by Rajmohan Rajaraman and Friedhelm Meyer auf der Heide. ACM, 2011 , pp. 149–158. /u.sc/r.sc/l.sc: htt...

arXiv 2011