Pith. sign in

REVIEW 2 major objections 4 minor 28 references

Byzantine Consensus in the Random Asynchronous Model

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

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

Pith's one-line read By replacing the adversarial message schedule with a random one, Byzantine consensus becomes solvable at resilience thresholds that standard asynchrony forbids.

desk verdict Random asynchronous model is a genuinely new relaxation that yields consensus at n=2f+1 and n=f+2; the positive results look right, but the core impossibility proof (Theorem 13) has a fixable gap. read the letter →

arxiv 2502.09116 v2 pith:SWAZZ32Y submitted 2025-02-13 cs.DC

George Danezis , Jovan Komatovic , Lefteris Kokoris-Kogias , Alberto Sonnino , Igor Zablotchi This is my paper · ORCID
classification cs.DC
keywords Byzantineconsensusrandomasynchronousmodelschedulernetworksfaulttoleranceimpossibilitypartialsynchronyadopt-commit
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 introduces the random asynchronous model, in which message delays remain unbounded and Byzantine faults remain, but the order of message delivery is chosen by a random scheduler instead of an adversary. It claims that this single change dissolves the main source of asynchronous impossibility: an adversary can no longer starve honest parties of communication. Concretely, it presents consensus protocols with deterministic strong safety and almost-sure termination at n=3f+1, deterministic termination with strong safety holding with high probability at n=2f+1, and deterministic weak validity and termination with high-probability agreement at n=f+2, together with matching impossibility results. If correct, the random asynchronous model sits strictly between asynchrony and synchrony and is incomparable with partial synchrony, which would explain why practical systems run asynchronous consensus without a randomness beacon.

What carries the argument

The central object is the random scheduler: at every step it draws a sender-receiver pair (p,q) from the set of pairs with a pending message, delivers the earliest pending message on that pair, and guarantees that each such pair is drawn with probability at least C(n,f)>0, conditionally independent of message history and message content. This pair-level draw, rather than a message-level draw, is what prevents Byzantine flooding from biasing the schedule. The protocols are deterministic and exploit the fact that favorable delivery orders have non-zero probability: a round-based adopt-commit procedure for n=3f+1, where a two-phase object either commits a value or adopts one while preserving consistency, and an f+1-phase threshold-signature propagation procedure for n=2f+1 and n=f+2. The impossibility results reuse FLP-style bivalent-state arguments against finite prefixes with positive probability.

What would settle it

Simulate Algorithm 3 with n=2f+1 on the specified pair-level random scheduler, increasing R, and measure the frequency of executions in which two correct processes end phase f+1 with different accepted-value sets; the theorem requires this frequency to decay exponentially in R, so any schedule family that keeps it non-negligible would falsify the high-probability agreement claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that the adversarial scheduler, not asynchrony itself, is what makes many Byzantine consensus tasks impossible: replacing the adversary's choice of delivery order with a random scheduler over sender-receiver pairs preserves unbounded delays and Byzantine faults while making protocols possible at thresholds where standard asynchrony, and even partial synchrony, forbids them. At n=3f+1 a round-based adopt-commit protocol yields deterministic strong validity and agreement with termination almost surely. At n=2f+1 an f+1-phase flooding protocol yields deterministic termination and strong validity and agreement with high probability. At n=f+2 the same protocol yields deterministic weak validity and termination with agreement holding with high probability. Matching impossibility results show these guarantees cannot be strengthened, and the paper argues the model is strictly stronger than asynchrony, strictly weaker than synchrony, and incomparable with partial synchrony.

Load-bearing premise

The model rests on the scheduler's pair-level fairness: at every delivery step, each sender-receiver pair with a pending message is chosen with probability at least C(n,f)>0, independently of message history and message content, so if a real or adversarial network can make some pair's draw probability arbitrarily small, the positive results no longer hold.

Editorial extensions

If this is right

  • At n=3f+1, Byzantine consensus is solvable with deterministic strong validity and agreement, and termination almost surely, without local randomness or a common coin.
  • At n=2f+1, strong Byzantine consensus is solvable with deterministic termination and strong validity and agreement holding with high probability, a setting impossible in standard asynchrony and in partial synchrony.
  • At n=f+2, weak Byzantine consensus is solvable with deterministic weak validity and termination while agreement holds with high probability.
  • No random-asynchronous protocol can achieve the stronger combinations: deterministic consensus with a single crash is impossible, at n=2f+1 almost-sure safety with deterministic termination is impossible, and at n=f+2 with f>=2 high-probability strong safety with deterministic termination is impossible.
  • The random asynchronous model is strictly stronger than asynchrony, strictly weaker than synchrony, and incomparable with partial synchrony in terms of task solvability.

Reading between the lines

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

  • Editorial inference: the pair-level fairness assumption suggests a testable engineering principle: Byzantine resilience under a random scheduler depends on the scheduler hiding message contents and volumes, so practical deployments would need an unpredictable permutation of pending sender-receiver pairs rather than a random message queue.
  • Editorial inference: the n=2f+1 protocol effectively implements a perfect failure detector with high probability via heartbeats, and the paper leaves open whether existing protocols that rely on perfect or eventually perfect failure detectors can be translated to use it.
  • Editorial inference: because the model sits between asynchrony and synchrony, one could investigate whether synchronous round-complexity lower bounds re-emerge in expectation or with high probability under random scheduling, giving quantitative tradeoffs the paper does not state.
  • Editorial inference: the impossibility results rely on finite prefixes having non-negligible probability, so changing the scheduler's lower-bound constant C(n,f) or the independence assumption is a design knob that could move the model closer to synchrony or back toward asynchrony.
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 / 4 minor

Summary. The paper proposes a new network model, the random asynchronous model, in which the order of message deliveries is governed by a random scheduler rather than an adversary, while message delays remain unbounded and Byzantine faults are preserved. The authors study Byzantine consensus at three resilience thresholds: for n=3f+1 they present a round-based protocol with deterministic validity and agreement and almost-sure termination; for n=2f+1 they give a phase-based protocol with deterministic termination and validity/agreement holding with high probability; for n=f+2 they show the same protocol achieves deterministic weak validity and termination with high-probability agreement. The paper complements these positive results with three impossibility theorems establishing matching bounds, and it compares the random asynchronous model with asynchrony, partial synchrony, and synchrony in terms of task solvability. The central claim is that removing adversarial scheduling makes consensus solvable at lower resilience thresholds than in the standard asynchronous model, while still preserving unbounded delays and Byzantine faults.

Significance. If the results hold, the paper makes a valuable conceptual contribution: it isolates the adversarial scheduler as the source of several asynchronous impossibility results and shows that a random scheduler, which is arguably closer to some practical systems, permits consensus at n=2f+1 and n=f+2 with probabilistic safety. The positive protocols are clean and their proofs are mostly detailed, and the use of standard components (Byzantine reliable broadcast, adopt-commit rounds) makes the construction credible. The machine-checkable or fully explicit proof style is a strength; the paper also gives concrete probabilistic bounds (e.g., Lemma 1) rather than only asymptotic arguments. The main caveat is that one of the impossibility proofs, Theorem 13, is not rigorously established as written, and its repair is nontrivial enough that the negative result at n=f+2 should not be taken at face value without a revised proof.

major comments (2)
  1. [Section 6, Theorem 13] The proof of Theorem 13 contains a load-bearing gap. It fixes a single all-correct heterogeneous execution E, takes the shortest deciding prefix π of its schedule, shows that π is bad for strong validity or agreement, and then concludes that the probability of π is non-negligible because π has finite length for fixed n and f. This inference is invalid for parameterized protocols: the length |π| can grow with the algorithm's parameter (e.g., R in Algorithm 3), and a single finite prefix can have probability at most C(n,f)^|π|, which may be exponentially small in that parameter. The contradiction with the requirement that the total probability of bad schedules be negligible requires the total bad probability to be non-negligible, not merely the existence of one bad prefix. The argument is repairable by observing that the E1, E2, E3 construction works for every valid schedule of an all-correct heterogeneous execution, so every such schedule has a bad prefix and the total bad probability is 1, but as written this universal quantification is missing. Because Theorem 13 is the matching negative result for the n=f+2 positive protocol, this gap must be fixed before the claim is established.
  2. [Section 6, Theorem 14] The proof of Theorem 14 is only a sketch and does not fully spell out the construction that leads to the contradiction. In particular, the phrase 'following the FLP proof, there exists an infinite bivalent execution E' and the subsequent step 'A must decide in a finite prefix π of E, when the state is still bivalent' need a precise argument showing that the decision in π, together with a second execution with the same prefix, violates strong validity or agreement. The result itself is standard and likely correct, and the finite-prefix non-zero-probability reasoning is valid for almost-sure impossibility, but the proof as written is too compressed for a formal paper.
minor comments (4)
  1. [Section 6, Theorem 11] The proof of Theorem 11 is a brief sketch; a more explicit reduction to the FLP impossibility would improve rigor, even if the argument is standard.
  2. [Section 2] The definition of 'with high probability' is informal about which parameter is used; the proofs of Lemma 1 and Theorem 3 make clear that R is the parameter, but the definition itself could state this more explicitly.
  3. [Section 3, Theorem 20] The Markov chain argument for almost-sure termination could be made more precise by specifying the lower bound on the transition probability to an absorbing state and applying a standard absorption argument; currently it is stated informally.
  4. [Section 7] The simulation of the random asynchronous model in synchrony is described in prose; a formal definition of the adapter and a proof that the induced schedule satisfies the random asynchronous model's probability lower bound would remove ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-citations are motivational only, and the formal results derive from the stated random-scheduler axioms and standard external impossibility results.

full rationale

The formal results are self-contained. Algorithms 1-3 are proved directly from the random-scheduler axioms (Eqs. (1)-(2)), BRB properties, and quorum/union-bound arguments; no parameter is fitted to a target outcome and no derived quantity is read back as an input. Self-citations to Tusk [11] and Mahi-Mahi [16] appear only as practical motivation and as claimed special cases in Related Work, so they are not load-bearing for any theorem. The negative results explicitly rest on the external FLP impossibility result. One non-circular correctness concern should be noted: in Section 6, Theorem 13, the proof fixes one all-correct heterogeneous execution E and infers from the finiteness of the deciding prefix pi that its probability is non-negligible; because |pi| can grow with the protocol parameter R and the paper defines negligible as exponential in 'some parameter of the algorithm', C(n,f)^{|pi|} can be negligible. The gap is repairable by quantifying over all valid schedules of an all-correct heterogeneous execution, but as printed the contradiction with 'with high probability' is not fully established. This is a proof-quantification issue, not a circular reduction of the model's conclusions to its assumptions.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claims rest on the random-scheduler definition, reliable links, authenticated channels, and standard BRB/FLP results. There are no data-fitted constants; R is a tunable parameter of Algorithm 3, and C(n,f) is an assumed model constant rather than a fitted value.

free parameters (1)
  • R
    Number of communication rounds per phase in Algorithm 3; the w.h.p. guarantees require R large enough that the failure probability n(n-1) exp(-R C(n,f)(n-f)) is negligible. R is a tunable security parameter rather than a fitted constant.
assumptions (5)
  • domain assumption Random scheduler: each sender-receiver pair with a pending message is drawn with probability at least C(n,f)>0, and draws are conditionally independent given the history.
    Defines the model and makes Byzantine flooding unable to bias the schedule. This is the load-bearing premise for all positive results, stated in Section 2, equations (1) and (2).
  • domain assumption Reliable point-to-point links with integrity and no-loss.
    Section 2 Network; needed for eventual delivery of messages from correct processes, used throughout the positive protocols.
  • domain assumption Authenticated channels and unforgeable digital signatures.
    Section 2 Cryptography; used by Algorithm 3 to count signed values and by the Byzantine Reliable Broadcast layer.
  • standard math Byzantine Reliable Broadcast properties: validity, no-duplication, integrity, consistency, totality.
    Section 3 and Appendix B; imported from Cachin et al. and used to build the n=3f+1 Round procedure.
  • standard math FLP impossibility theorem and its bivalent execution construction.
    Used in Theorems 11 and 14 to establish negative results for protocols with deterministic termination.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Byzantine Consensus in the Random Asynchronous Model." pith.science (2026). https://pith.science/paper/SWAZZ32Y

@misc{pith2026250209116,
  author       = {Pith},
  title        = {Pith review of: Byzantine Consensus in the Random Asynchronous Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SWAZZ32Y}},
  note         = {Machine review of arXiv:2502.09116}
}
abstract

We propose a novel relaxation of the classic asynchronous network model, called the random asynchronous model, which removes adversarial message scheduling while preserving unbounded message delays and Byzantine faults. Instead of an adversary dictating message order, delivery follows a random schedule. We analyze Byzantine consensus at different resilience thresholds ($n=3f+1$, $n=2f+1$, and $n=f+2$) and show that our relaxation allows consensus with probabilistic guarantees which are impossible in the standard asynchronous model or even the partially synchronous model. We complement these protocols with corresponding impossibility results, establishing the limits of consensus in the random asynchronous model.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 18 canonical work pages

  1. [1]

    Aiyer, Lorenzo Alvisi, and Rida A

    Amitanand S. Aiyer, Lorenzo Alvisi, and Rida A. Bazzi. On the availability of non-strict quorum systems. In Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings , volume 3724, pages 48--62. Springer, 2005. https://doi.org/10.1007/11561927\_6 doi:10.1007/11561927\_6

    doi:10.1007/11561927 2005

  2. [2]

    Are lock-free concurrent algorithms practically wait-free? J

    Dan Alistarh, Keren Censor - Hillel, and Nir Shavit. Are lock-free concurrent algorithms practically wait-free? J. ACM , 63(4):31:1--31:20, 2016. URL: https://doi.org/10.1145/2903136

    work page doi:10.1145/2903136 2016

  3. [3]

    Lock-free algorithms under stochastic schedulers

    Dan Alistarh, Thomas Sauerwald, and Milan Vojnovic. Lock-free algorithms under stochastic schedulers. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti \' a n, Spain, July 21 - 23, 2015 , pages 251--260. ACM , 2015. URL: https://doi.org/10.1145/2767386.2767430

    arXiv 2015

  4. [4]

    Fast deterministic consensus in a noisy environment

    James Aspnes. Fast deterministic consensus in a noisy environment. J. Algorithms , 45(1):16--39, 2002. URL: https://doi.org/10.1016/S0196-6774(02)00220-1

    work page doi:10.1016/s0196-6774(02)00220-1 2002

  5. [5]

    Probabilistic byzantine fault tolerance

    Diogo Avelas, Hasan Heydari, Eduardo Alchieri, Tobias Distler, and Alysson Bessani. Probabilistic byzantine fault tolerance. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024 , pages 170--181. ACM , 2024. https://doi.org/10.1145/3662158.3662810 doi:10.1145/3662158.3662810

    work page arXiv 2024

  6. [6]

    Sok: Consensus in the age of blockchains

    Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. Sok: Consensus in the age of blockchains. In AFT , 2019

    work page 2019

  7. [7]

    Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract)

    Michael Ben - Or. Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 17-19, 1983 , pages 27--30. ACM , 1983. https://doi.org/10.1145/800221.806707 doi:10.1145/800221.806707

    arXiv 1983

  8. [8]

    Asynchronous consensus and broadcast protocols

    Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. J. ACM , 32(4):824--840, 1985. https://doi.org/10.1145/4221.214134 doi:10.1145/4221.214134

    work page arXiv 1985

Show all 28 references
  1. [9]

    Christian Cachin, Rachid Guerraoui, and Lu \' s E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.) . Springer, 2011. https://doi.org/10.1007/978-3-642-15260-3 doi:10.1007/978-3-642-15260-3

    2011 doi

  2. [10]

    Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract)

    Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 16-19, 2000...

  3. [11]

    Narwhal and tusk: a dag-based mempool and efficient BFT consensus

    George Danezis, Lefteris Kokoris - Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and tusk: a dag-based mempool and efficient BFT consensus. In EuroSys '22: Seventeenth European Conference on Computer Systems, Rennes, France, April 5 - 8, 2022 , pages 34--50. ACM ,...

    2022

  4. [12]

    Consensus in the presence of partial synchrony

    Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM) , 35(2):288--323, 1988

    1988

  5. [13]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. In Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983 , pages 1--7. ACM , 1983. https://doi.org/10.114...

    1983

  6. [14]

    Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)

    Eli Gafni. Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, June 28 - July 2, 1998 , pages 143--152. ACM , 1998. https://doi.org/10.1145/277697....

    1998

  7. [15]

    An Empirical Study of Consensus Protocols’ DoS Resilience

    Giacomo Giuliari, Alberto Sonnino, Marc Frei, Fabio Streun, Lefteris Kokoris-Kogias, and Adrian Perrig. An Empirical Study of Consensus Protocols’ DoS Resilience . In ACM ASIACCS , 2024

    2024

  8. [16]

    Mahi-mahi: Low-latency asynchronous bft dag-based consensus

    Philipp Jovanovic, Lefteris Kokoris Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. Mahi-mahi: Low-latency asynchronous bft dag-based consensus. arXiv preprint arXiv:2410.08670 , 2024

    2024 arXiv

  9. [17]

    All You Need is DAG

    Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All You Need is DAG . In ACM PODC , 2021

    2021

  10. [18]

    The weak byzantine generals problem

    Leslie Lamport. The weak byzantine generals problem. J. ACM , 30(3):668--676, 1983. https://doi.org/10.1145/2402.322398 doi:10.1145/2402.322398

    1983

  11. [19]

    Shostak, and Marshall C

    Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst. , 4(3):382--401, 1982. https://doi.org/10.1145/357172.357176 doi:10.1145/357172.357176

    1982

  12. [20]

    Reiter, Avishai Wool, and Rebecca N

    Dahlia Malkhi, Michael K. Reiter, Avishai Wool, and Rebecca N. Wright. Probabilistic quorum systems. Inf. Comput. , 170(2):184--206, 2001. URL: https://doi.org/10.1006/inco.2001.3054, https://doi.org/10.1006/INCO.2001.3054 doi:10.1006/INCO.2001.3054

    2001

  13. [21]

    RITAS: services for randomized intrusion tolerance

    Henrique Moniz, Nuno Ferreira Neves, Miguel Correia, and Paulo Ver \' ssimo. RITAS: services for randomized intrusion tolerance. IEEE Trans. Dependable Secur. Comput. , 8(1):122--136, 2011. https://doi.org/10.1109/TDSC.2008.76 doi:10.1109/TDSC.2008.76

    2011 doi

  14. [22]

    Signature-free asynchronous binary byzantine consensus with t < n/3 , o(n^2) messages, and o(1) expected time

    Achour Most \' e faoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary byzantine consensus with t < n/3 , o(n^2) messages, and o(1) expected time. J. ACM , 62(4):31:1--31:21, 2015. https://doi.org/10.1145/2785953 doi:10.1145/2785953

    2015 doi

  15. [23]

    Michael O. Rabin. Randomized byzantine generals. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983 , pages 403--409. IEEE Computer Society, 1983. https://doi.org/10.1109/SFCS.1983.48 doi:10.1109/SFCS.1983.48

    1983 doi

  16. [24]

    Implicit Consensus: Blockchain with Unbounded Throughput , 2017

    Zhijie Ren, Kelong Cong, Johan Pouwelse, and Zekeriya Erkin. Implicit Consensus: Blockchain with Unbounded Throughput , 2017. https://arxiv.org/abs/1705.11046 arXiv:1705.11046

    2017 arXiv

  17. [25]

    Bullshark: DAG BFT protocols made practical

    Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris - Kogias. Bullshark: DAG BFT protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022 , p...

    2022

  18. [26]

    Structured derivations of consensus algorithms for failure detectors

    Jiong Yang, Gil Neiger, and Eli Gafni. Structured derivations of consensus algorithms for failure detectors. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, Puerto Vallarta, Mexico, June 28 - July 2, 1998 , pages 297--30...

    1998

  19. [27]

    Signed quorum systems

    Haifeng Yu. Signed quorum systems. Distributed Comput. , 18(4):307--323, 2006. URL: https://doi.org/10.1007/s00446-005-0133-8, https://doi.org/10.1007/S00446-005-0133-8 doi:10.1007/S00446-005-0133-8

    2006 doi

  20. [28]

    Waterbear: Practical asynchronous BFT matching security guarantees of partially synchronous BFT

    Haibin Zhang, Sisi Duan, Boxin Zhao, and Liehuang Zhu. Waterbear: Practical asynchronous BFT matching security guarantees of partially synchronous BFT . In 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023 , pages 5341--5357. USENIX Asso...

    2023

Pith tools

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