{"id":"f0ff4382-28f4-4990-a329-44136923697e","arxiv_id":"2502.09116","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Random message scheduling makes Byzantine consensus possible at n=2f+1 and n=f+2 with probabilistic safety, with matching impossibility results.","lead":"This paper introduces a model of asynchronous networks where message arrival order is random rather than adversarial, and shows that Byzantine consensus becomes possible with fewer replicas than standard bounds allow. It matters because it offers a theoretical explanation for why some practical blockchain protocols avoid cryptographic randomness, and it maps what is gained and lost by giving up adversarial scheduling.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 13's proof shows only a single finite bad prefix; its probability may be negligible in the protocol's own parameter, so the n=f+2 high-probability impossibility is not established as written, though the proof appears repairable by quantifying over all schedules.","rationale":"The positive results are the strongest part of the paper, and I do not see an internal inconsistency in the main protocols: the n=3f+1 round-based argument and the n=2f+1 phase-based signature accumulation both rely only on pair-level fairness, and the proofs of Lemmas 1-7 appear sound. The paper's own model assumption (Section 2) is explicitly an abstraction, not a claim about real networks, so I do not treat it as a correctness flaw. The genuine weakness is Theorem 13: the printed non-negligibility step proves only that one chosen finite prefix is bad, whereas the paper's definition of 'with high probability' requires the total probability of bad schedules to be negligible as a function of some protocol parameter. A finite prefix can have probability C^{|pi|}, which may be negligible if |pi| grows with a protocol parameter. The repair is short—quantify over all valid schedules rather than one execution—and I see no obstacle to it, so this is a proof gap rather than a refutation. Because the reader's verdict is already CONDITIONAL and this concern does not invalidate the central positive claims, I recommend leaving the verdict unchanged pending the proof patch.","tokens_in":18499,"tokens_out":19030,"duration_ms":210640,"concrete_test":"Rewrite the proof of Theorem 13 to start with an arbitrary valid schedule S of an all-correct heterogeneous execution, and verify that the E1-E3 indistinguishability argument yields a bad finite prefix of S in every case, using only deterministic termination and validity of S. If the construction goes through for every S, the theorem is restored; if there is a family of schedules whose bad prefixes have total probability negligible in the protocol's parameter, then the high-probability impossibility for n=f+2 does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 6, Theorem 13 argues that no n=f+2 protocol can have deterministic termination with strong validity and agreement holding with high probability. The proof fixes one all-correct heterogeneous execution E, takes the shortest deciding prefix pi of its schedule S, and shows via executions E1, E2, E3 that pi is a bad prefix. It then asserts that because pi has finite length, its probability is non-negligible. That inference is not justified: for a parameterized protocol (e.g., one with R rounds), |pi| and therefore C(n,f)^{|pi|} can grow with the parameter, and a single bad prefix can have exponentially small probability. The contradiction with 'with high probability' requires the total probability of bad schedules to be non-negligible. The argument is likely repairable by observing that the E1-E3 construction works for every valid schedule of an all-correct heterogeneous execution, so every schedule has a bad prefix and the total bad probability is 1. But as printed, this key quantification is missing, so the negative result at n=f+2 is not rigorously established. The positive protocols in Sections 3-5 do not depend on this proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18694,"tokens_out":14799,"duration_ms":135714,"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":[{"comment":"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.","section":"Section 6, Theorem 13"},{"comment":"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.","section":"Section 6, Theorem 14"}],"minor_comments":[{"comment":"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.","section":"Section 6, Theorem 11"},{"comment":"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.","section":"Section 2"},{"comment":"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.","section":"Section 3, Theorem 20"},{"comment":"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.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper introduces the random asynchronous model, where a random scheduler replaces the adversarial scheduler, and shows consensus at n=2f+1 and n=f+2 with probabilistic safety—something impossible under standard asynchrony or partial synchrony. The model is well-motivated and the positive results look correct.\n\nWhat's genuinely new: the scheduler draws sender-receiver pairs with a lower-bounded probability, which prevents Byzantine flooding from controlling delivery order. Under this model, the n=2f+1 protocol (deterministic termination, safety w.h.p.) and the n=f+2 weak consensus are real advances. The n=3f+1 protocol is basically an adopt-commit with the schedule playing the role of a common coin; the authors acknowledge this. The positive proofs are detailed and mostly sound. Lemma 1's coupling argument is a bit terse but works. The termination Markov chain arguments are fine.\n\nThe soft spot is the impossibility section, specifically Theorem 13. The proof fixes one schedule, takes its shortest deciding prefix, and claims the prefix has non-negligible probability because it's finite. That doesn't follow: the prefix length can depend on the protocol's own parameter (like R), and its probability can be exponentially small. The theorem is probably right, and the fix is straightforward—the E1-E3 construction works for every schedule of an all-correct heterogeneous execution, so every schedule has a bad prefix and the total bad probability is 1, not negligible. But as printed, the proof doesn't establish the contradiction. Theorem 14's proof is fine because it only needs positive probability, not non-negligibility. Section 7's model-comparison arguments are informal, especially the synchrony simulation, but the conclusions are plausible.\n\nVerdict: this deserves a serious referee. The core idea is important, the positive results are novel and appear correct, and the negative-result gap is repairable. I'd want to see a corrected proof of Theorem 13 and a cleaner treatment of the model comparisons before accepting. For the right audience—distributed algorithms, blockchain consensus—it's a worthwhile read. I'd bring it to the reading group and would cite it in work on scheduler assumptions.","headline":"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.","tokens_in":19257,"tokens_out":6631,"would_cite":true,"duration_ms":64688,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"By replacing the adversarial message schedule with a random one, Byzantine consensus becomes solvable at resilience thresholds that standard asynchrony forbids.","keywords":["Byzantine consensus","random asynchronous model","random scheduler","asynchronous networks","Byzantine fault tolerance","consensus impossibility","partial synchrony","adopt-commit"],"falsifier":"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.","tokens_in":18287,"feed_emoji":"🎲","tokens_out":6632,"duration_ms":57018,"temperature":0.7,"pith_summary":"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.","feed_headline":"Random message order cracks Byzantine consensus limits","feed_subtitle":"Deterministic or high-probability safety at n=3f+1, n=2f+1, and n=f+2 replaces adversarial scheduling.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"FLP impossibility of deterministic asynchronous consensus is the baseline the random schedules circumvent.","marker":"[13]"},{"why":"Partial-synchrony impossibility for n<3f+1 is used to show the random asynchronous model is incomparable with partial synchrony.","marker":"[12]"},{"why":"Supplies Byzantine reliable broadcast and failure detector background used by the n=3f+1 protocol and by the comparison tasks.","marker":"[9]"},{"why":"Defines the fair scheduler abstraction that motivates random scheduling and is cited for the network-partition argument.","marker":"[8]"},{"why":"Used with [8] for the standard network-partition argument showing the n=2f+1 task is impossible in pure asynchrony.","marker":"[7]"},{"why":"Precedent for noisy and randomized scheduling in shared memory that the model extends to message passing.","marker":"[4]"},{"why":"Practical DAG-based BFT whose production experience without a random coin motivates the model.","marker":"[11]"},{"why":"Another DAG-based BFT whose random scheduler is described as a special case of the proposed one.","marker":"[16]"},{"why":"The adopt-commit object that the round procedure for n=3f+1 is modeled on.","marker":"[14]"}],"fun_headline_variants":["Random scheduling unlocks Byzantine consensus","Adversary out, random delays in: Byzantine solved","Byzantine consensus thrives under random message order","Random async model shatters classic impossibility"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random scheduling unlocks Byzantine consensus","Adversary out, random delays in: Byzantine solved","Byzantine consensus thrives under random message order","Random async model shatters classic impossibility"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1258,"prompt_tokens":820,"completion_tokens":438,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":383}},"tokens_in":436,"tokens_out":438,"duration_ms":4616,"temperature":1.0,"reasoning_tokens":383,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T22:38:50.141594+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Fischer, Nancy A","cited_arxiv_id":null,"evidence_quote":"FLP impossibility of deterministic asynchronous consensus is the baseline the random schedules circumvent."},{"cited_title":"Consensus in the presence of partial synchrony","cited_arxiv_id":null,"evidence_quote":"Partial-synchrony impossibility for n<3f+1 is used to show the random asynchronous model is incomparable with partial synchrony."},{"cited_title":"Asynchronous consensus and broadcast protocols","cited_arxiv_id":null,"evidence_quote":"Defines the fair scheduler abstraction that motivates random scheduling and is cited for the network-partition argument."},{"cited_title":"Fast deterministic consensus in a noisy environment","cited_arxiv_id":null,"evidence_quote":"Precedent for noisy and randomized scheduling in shared memory that the model extends to message passing."},{"cited_title":"Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)","cited_arxiv_id":null,"evidence_quote":"The adopt-commit object that the round procedure for n=3f+1 is modeled on."}],"review_version":1}