Beyond Leaderless: Randomized Consensus Against Mobile Crashes
Ittai Abraham, Kaya Alpturer, Pranav Garimidi, Joachim Neu, Tim Roughgarden, Ertem Nusret Tas
Clean, well-motivated protocol with rigorous safety/liveness proofs addressing a real gap in multi-proposer consensus, but with no real implementation and a narrow adversary model.
Abstract
Many consensus protocols fail to terminate under attack from an adversary that has the power to move between replicas and repeatedly crash one of them, even in synchrony. We present Multi-Leader Fixed-View Simplex (ML-FVS) to defend against such an adversary while keeping the simple structure and good-case latency of Simplex consensus. Our protocol extends fixed-view Simplex with multiple leaders, each of which may broadcast a proposal. At the voting deadline, each replica votes on the set of proposals it has seen so far. A hidden threshold beacon revealed after the votes gives a priority order on the multiple leaders, resolving each vote to its highest-priority proposal. Our model combines permanent adaptive Byzantine faults with mobile crashes. For a constant crash budget and -delayed Byzantine corruption, we obtain expected latency over repeated views whose leaders start honest. With immediate Byzantine corruptions, the protocol still achieves liveness. We also evaluate the protocol under random network delays and stochastic faults, finding that multiple leaders reduce view failures even when rational leaders delay their proposals to increase rewards.
AI Impact Assessments
(1 model)Core Contribution
The paper presents ML-FVS, a Simplex-style consensus protocol with a fixed view schedule that tolerates mobile crashes. The problem is an adversary that moves between replicas and repeatedly crashes the current leader, mid-broadcast if it likes. Deterministic protocols cannot terminate against this adversary (Santoro–Widmayer). Existing multi-proposer designs such as Cadence and Mysticeti, and leaderless designs such as BFT-Archipelago, handle mobile suspension but not crashes that interrupt a broadcast. The design uses k = c+1 public leaders per view. Each replica votes on the set of proposals it has seen, and the vote carries a threshold-beacon share. Once 2f+1 shares reveal a hidden random priority order, every vote resolves to its highest-priority proposal. Because the order is revealed after the adversary has committed to which broadcasts to interrupt, a completed proposal ranks first with probability at least 1/k. In the good case, with c+1 leaders and c crashes, at least one leader completes its broadcast. Each view then finalizes with probability at least 1/(c+1) within 3Δ, giving expected latency 3Δ(c+1). The paper also proves liveness under immediate Byzantine corruption, using a leader-sampling argument plus the fact that only finitely many corruptions can occur. A simulation/equilibrium section shows that a second leader cuts view failure from about 1% to about 0.01% even when rational leaders delay proposals.
The idea is elegant: delayed selection through a hidden beacon, as in VABA, applied to a small leader set and compatible with Simplex's good-case latency. The "vote on the set, resolve afterward" trick is the key mechanism. The paper explains why a single leader fails (Lemma 12), why known priorities fail (Example 1), and why Cadence and Mysticeti stall under a mid-broadcast crash. This gives the contribution a clear conceptual story.
Methodological Rigor
Safety rests on quorum intersection and is clean. The liveness proofs are careful. They cover the budget-refund model that keeps an active honest quorum (Lemma 5), certificate catch-up, and the coupling argument for adversaries that start new corruptions. The sampling bound q(b) and its minimization at b = f−c are handled properly. Several limitations remain:
The empirical part is an analytic or enumerative computation under a model, not a real implementation. It uses CloudPing latency distributions, a 1% stall probability, and a timing game with a rational-leader best-response grid. Its main finding, that failure drops from 1% to 0.01% (essentially p → p²), is almost an immediate consequence of the model and of Theorem D.1 (failure probability p^k). So the evaluation is illustrative rather than strong evidence. It does not exercise mobile crashes, and no end-to-end implementation or throughput and latency measurements are reported. The stall model assumes independence across leaders.
Potential Impact
The result is mostly theoretical and conceptual. It is relevant to blockchain consensus designers working on multiple concurrent proposers (MCP, Cadence, Mysticeti, Barnacle). It offers a minimal, Simplex-compatible way to get resilience to partial-broadcast crashes. Practical adoption is uncertain. The threat model of a mobile crash adversary is somewhat niche, though leader-targeted DoS is a real concern in public blockchains. Resilience to targeted leader attacks at about 2 leaders and 6Δ expected latency under attack is attractive. The timing-game analysis connects to the MEV and timing-games literature and shows multi-leader designs remain robust under rational delay, a useful practical observation. The mobile-crash versus suspension distinction and the attack executions on Cadence and Mysticeti add some refutation or clarification value, though they are limited to specific protocols' fast paths or ordering and are not general refutations.
Timeliness
Multi-proposer consensus is currently a hot area in blockchain research (Cadence, MCP, Barnacle, Prefix Consensus). Simplex and its fixed-view variants are gaining attention. The paper fits this moment well.
Strengths
Limitations
Overall this is a solid, well-motivated distributed-computing theory paper with moderate influence expected in the blockchain consensus community.
Generated Nov 3, 2026
Comparison History (0)
Clean, well-motivated protocol with rigorous safety/liveness proofs addressing a real gap in multi-proposer consensus, but with no real implementation and a narrow adversary model.