Why Canonical Rounds Fail for Optimal Byzantine Resilience
Pith reviewed 2026-05-18 10:19 UTC · model grok-4.3
The pith
Canonical rounds are incompatible with optimal Byzantine resilience for consensus even with randomization.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
When 3f < n ≤ 5f, no randomized canonical-round algorithm solves consensus with bounded expected round complexity, communication-closed variants solve neither consensus nor its relaxations, and the same impossibilities hold for reliable broadcast and gather; bounded canonical-round algorithms exist when n > 5f, so optimal resilience n > 3f is impossible inside the canonical-round framework.
What carries the argument
The canonical asynchronous round abstraction, which structures message exchanges so that asynchronous executions appear synchronous, together with the notion of nontrivial convergence that unifies lower bounds for consensus and its classical relaxations.
If this is right
- No randomized canonical-round algorithm achieves bounded expected round complexity for consensus when 3f < n ≤ 5f.
- Communication-closed canonical-round algorithms fail to solve consensus entirely in the same regime.
- The impossibility carries over to reliable broadcast and gather by simple reductions.
- Bounded canonical-round algorithms for these problems exist only when n > 5f.
- The gather primitive supplies the content-dependent communication needed to reach optimal resilience for connected consensus.
Where Pith is reading between the lines
- Designers seeking optimal Byzantine resilience should consider communication structures outside the canonical-round model.
- The gap between the 3f and 5f thresholds quantifies the resilience cost imposed by requiring canonical rounds.
- Similar round-based abstractions in other distributed problems may need re-examination for their effect on fault tolerance.
Load-bearing premise
Any algorithm under consideration must be expressed using the canonical-round abstraction or its communication-closed variants rather than arbitrary message patterns.
What would settle it
An explicit randomized canonical-round algorithm that solves consensus with bounded expected round complexity for some n satisfying 3f < n ≤ 5f would disprove the central impossibility.
read the original abstract
Canonical asynchronous rounds are a widely used abstraction for structuring distributed algorithms, making asynchronous executions appear synchronous and enabling modular reasoning. We show that this abstraction is fundamentally incompatible with optimal resilience in the Byzantine setting, even when randomization is allowed. Specifically, we prove that when $3f < n \le 5f$, where $n$ is the number of processes and at most $f$ may be Byzantine faulty, no randomized canonical-round algorithm can solve consensus with bounded expected round complexity, and that communication-closed variants fail to solve consensus altogether in this regime. We establish these lower bounds via a unifying notion of nontrivial convergence, which captures consensus as well as classical relaxations, such as approximate agreement and connected consensus. Using simple reductions, the same impossibility extends to fundamental communication primitives such as reliable broadcast and gather. Our results identify a sharp boundary: while bounded canonical-round algorithms for these problems exist when $n > 5f$, they cannot when $n \le 5f$. Thus optimal resilience, $n > 3f$, cannot be achieved within the canonical-round framework. On the positive side, we show that the gather primitive captures the content-dependent communication needed to bypass this limitation. We use gather to obtain a simple and modular algorithm for connected consensus with optimal resilience, clarifying the communication structures required for optimal resilience.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that the canonical asynchronous rounds abstraction is incompatible with optimal Byzantine resilience (n > 3f) for consensus and related problems when 3f < n ≤ 5f, even with randomization. It proves via reductions from a unifying notion of nontrivial convergence that communication-closed canonical-round algorithms fail to solve consensus entirely in this regime, while general randomized canonical-round algorithms cannot achieve bounded expected round complexity. The same impossibilities extend to primitives such as reliable broadcast and gather. A positive result shows that the gather primitive enables a simple modular algorithm for connected consensus at optimal resilience (n > 3f), identifying content-dependent communication as the missing ingredient and establishing 5f as a sharp boundary for bounded canonical-round solutions.
Significance. If the results hold, the work is significant because it supplies a precise explanation for the well-known resilience gap (n > 5f) in many canonical-round Byzantine algorithms and demonstrates that optimal resilience requires abandoning communication-closed or round-structured patterns. The explicit positive construction for connected consensus supplies independent evidence that the 5f threshold is meaningful rather than an artifact, and the unifying nontrivial-convergence framework allows the impossibility to apply cleanly across consensus, approximate agreement, and connected consensus. These findings are likely to influence protocol design in asynchronous Byzantine systems by highlighting the necessity of content-dependent communication.
major comments (2)
- [§4] §4 (Definition of nontrivial convergence and its reductions): the central lower bounds rest on this unifying notion capturing consensus as well as the listed relaxations; however, the manuscript does not explicitly verify that the reduction from asynchronous Byzantine executions preserves the nontrivial-convergence property for connected consensus, which is load-bearing for extending the impossibility to that problem.
- [§5.1] §5.1 (Randomized general canonical rounds): the argument that expected round complexity must be unbounded when 3f < n ≤ 5f relies on an adversary that forces divergence while respecting the canonical-round structure; the handling of private randomness and how it interacts with the communication-closed restriction in the reduction needs an explicit lemma showing that no distribution over round schedules can bound the expectation.
minor comments (3)
- [Abstract] The abstract introduces 'communication-closed variants' without a forward reference to their formal definition; adding a parenthetical pointer to the relevant subsection would aid readers.
- [Positive construction section] In the positive construction (gather-based connected consensus), the pseudocode would benefit from inline comments clarifying which messages carry content-dependent information that bypasses the canonical-round limitation.
- [Throughout] Notation for the resilience parameter (3f < n ≤ 5f) is used consistently, but a single summary table comparing the four regimes (n > 5f, 3f < n ≤ 5f, etc.) for each primitive would improve clarity.
Simulated Author's Rebuttal
We thank the referee for the positive assessment and constructive comments. We address the two major comments below and will incorporate clarifications in the revised manuscript.
read point-by-point responses
-
Referee: [§4] §4 (Definition of nontrivial convergence and its reductions): the central lower bounds rest on this unifying notion capturing consensus as well as the listed relaxations; however, the manuscript does not explicitly verify that the reduction from asynchronous Byzantine executions preserves the nontrivial-convergence property for connected consensus, which is load-bearing for extending the impossibility to that problem.
Authors: We agree that an explicit verification would improve clarity. The reduction preserves the nontrivial-convergence property for connected consensus because the executions are a special case of those used for consensus, and the output-function definition is invariant under the Byzantine simulation. In the revision we will add a short supporting paragraph in §4 that walks through this preservation explicitly for connected consensus. revision: yes
-
Referee: [§5.1] §5.1 (Randomized general canonical rounds): the argument that expected round complexity must be unbounded when 3f < n ≤ 5f relies on an adversary that forces divergence while respecting the canonical-round structure; the handling of private randomness and how it interacts with the communication-closed restriction in the reduction needs an explicit lemma showing that no distribution over round schedules can bound the expectation.
Authors: We agree that an explicit lemma would strengthen the presentation. In the revised manuscript we will insert a new lemma in §5.1 proving that, for any distribution over round schedules, an adversary respecting the communication-closed restriction can still force unbounded expected round complexity. The lemma will explicitly address how private randomness is handled by considering adaptive Byzantine behavior that observes messages without violating the round structure. revision: yes
Circularity Check
No significant circularity
full rationale
The paper establishes impossibility results for canonical-round algorithms via reductions to an external asynchronous Byzantine execution model and a unifying definition of nontrivial convergence that captures multiple problems. These are formal lower-bound arguments rather than self-referential definitions or fitted predictions. The positive construction of a gather-based algorithm for connected consensus at optimal resilience (n > 3f) supplies independent evidence that the 5f boundary is meaningful and that content-dependent communication is the distinguishing factor. No load-bearing self-citations, ansatzes smuggled via prior work, or renamings of known results appear in the derivation; the scope is explicitly limited to algorithms expressible in the abstraction, making the argument self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Asynchronous message-passing model with up to f Byzantine faults
- domain assumption Canonical rounds abstraction structures all communication into synchronized phases
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.