Multivalued Consensus: General Adversaries Require More Communication
Mose Mizrahi, Roger Wattenhofer
cs.DC, cs.CR, cs.IT
2026-08-19
ETH Zurich builds adversary structures from projective geometry: consensus against general (non-threshold) adversaries needs Ω(Ln^(1+1/d)) bits instead of the threshold-tight Ω(Ln); a non-terminating protocol escapes the async bound near Ln.
Fault-tolerant consensus is usually studied against a threshold adversary that corrupts at most t nodes, with tasks solvable when t < n/3 or t < n/2. Real deployments often have messier trust assumptions, captured by a general adversary structure Z: a family of sets where the adversary may corrupt every node in any one set. Solvability under the resulting Q^d condition (no d sets in Z cover all n nodes) has been settled for decades. Efficiency has not. Synchronous binary byzantine agreement costs O(n²) bits against t < n/3, but the best known protocol against general Q³ adversaries costs O(n³). The gap bites hardest for long inputs: the erasure-coding machinery that makes L-bit consensus cost a tight Ω(Ln) against thresholds can degrade to O(Ln²) against general adversaries, because the guaranteed count of correct parties can drop to O(1) and coded symbols blow up. The paper asks whether that penalty is an artifact of technique or a fundamental cost.
The answer comes from an explicit worst-case adversary built out of d-dimensional finite projective geometry PG(d,q) with q = Θ(n^{1/d}). Each party is a point; each hyperplane defines a quorum; the adversary corrupts everything outside some hyperplane. The useful property is that each point lies on Θ(n^{-1/d}·|S|) hyperplanes, so a large family of quorums overlaps heavily while each quorum stays small.
The lower-bound argument combines an entropy bound with double counting. For reliable broadcast, the sender holds a uniformly random L-bit input and the adversary delays all messages from outside a quorum U, forcing U's parties to output and terminate without hearing from the rest. For every quorum S and every outside party i, the parties in S must send i Ω(L) bits before terminating: from S's viewpoint, everyone outside S ∪ {i} could be faulty, so i must learn a uniform random value from S's messages alone, which is information-theoretically impossible below Ω(L) bits. Summing over all (S, i) pairs gives Ω(|S|·Ln); since each party belongs to only Θ(n^{-1/d}·|S|) quorums, each transmitted bit is counted at most that many times, leaving Ω(Ln^{1+1/d}).
Five tasks get five bounds: synchronous interactive consistency Ω(Ln^{2+1/d}), synchronous byzantine agreement and broadcast Ω(Ln^{1+1/d}), asynchronous reliable broadcast and byzantine agreement Ω(Ln^{1+1/d}), asynchronous core set agreement Ω(Ln^{2+1/d}). The asynchronous bounds need only send-omission faults, weaker than byzantine, and survive cryptography.
The sharpest finding concerns termination. The authors design PullCast, a non-terminating reliable broadcast protocol: after outputting, parties keep serving on-demand requests for erasure-coded fragments, with requests dynamically routed toward fast responders, much like BitTorrent. It is perfectly secure against any general-omission adversary at (1 + 1/(δ-1))Ln + O(δn² log(δn)) bits, arbitrarily close to Ln for large δ. That beats the Ω(Ln^{1+1/d}) bound, and it shows the bound's weak point is termination: a terminating quorum must blindly push redundancy to parties it cannot see, while a non-terminating one can wait and answer pulls. A companion Term protocol adds termination after agreement for O(Ln^{1+1/d} + n² log n) bits under the Q^d condition, which matches the asynchronous lower bound and proves it tight.
| Task | Setting | Lower bound | Threshold adversary |
| Interactive consistency | sync, error-free, d≥3 | Ω(Ln^{2+1/d}) | Ω(Ln²), output-driven |
| Byzantine agreement/broadcast | sync, error-free, d≥3 | Ω(Ln^{1+1/d}) | Ω(Ln), tight |
| Reliable broadcast | async, send-omission, d≥1 | Ω(Ln^{1+1/d}) | Ω(Ln), tight |
| Async byzantine agreement | send-omission, d≥2 | Ω(Ln^{1+1/d}) | Ω(Ln) |
| Core set agreement | async, send-omission, d≥2 | Ω(Ln^{2+1/d}) | Ω(Ln²) |
On the positive side, PullCast costs (1 + 1/(δ-1))Ln + O(δn²log(δn)) bits with latency 2(δ-1)n-1, and Term lifts any agreement protocol to termination for O(Ln^{1+1/d} + n²log n) additional bits, together matching the asynchronous bound. PullCast also shows that Locher's (1.5-o(1))Ln lower bound does not extend to non-terminating protocols, beating it under a stronger fault model.
Consortium chains and cross-institution multiparty systems rarely have uniform trust; their assumptions look like "these parties will not fail together", which is exactly a general adversary structure. This paper is the first systematic quantification of what that finer trust granularity costs: a factor of n^{1/d} on communication for long-value consensus, where d is the order of the trust assumption. Engineers porting erasure-coded broadcast from threshold designs should expect that factor, not a constant overhead.
The termination loophole is directly actionable. Long-running services such as replicated state machines never terminate anyway, and PullCast-style pull-based broadcast lands squarely in the exempt zone, achieving near-optimal Ln communication.
The synchronous bounds hold only for error-free protocols. Once a negligible failure probability is allowed, an O(Ln + κ·poly(n)) protocol exists for every adversary structure, because input hashing makes checking agreement cheap; the authors state this restriction is essential, which limits the synchronous results to theoretical interest. The bounds also require minimum input lengths such as L = Ω(Rn^{1-1/d}), because parties can encode metadata in silence; the authors note that tagged messages or an entropy-based measure would remove the restriction, so part of the bound rests on modeling choices. Synchronous tightness is only conjectured, with no matching upper bound. The adversary structures exist only for specific n values tied to prime powers, though consecutive such values become dense as n grows. PullCast's latency is 2(δ-1)n-1, and pushing communication toward Ln requires δ close to 1, which pushes latency to Θ(n) hops, a trade-off that may not suit latency-sensitive deployments.