The open problems in consensus.

Phase 10 closes not with a solved problem but with an honest map of what remains unsolved. Every algorithm this series has covered — from article 3.3's majority-overlap quorums through Meerkat's every-replica-writable design (10.3) — operates within a set of assumptions (classical fault models, honest-but-limited adversaries, non-quantum cryptography, human-scale request rates) that newer forces are starting to strain. This closing article of Phase 10 names four genuinely open problems the field has not settled, gives each the same honest treatment article 10.1 taught this series to demand of any paper, and sets up Phase 11's forward-looking material.

Post-quantum Byzantine consensus

Every Byzantine consensus protocol this series covered in Phase 6 — PBFT's authenticator scheme, HotStuff's threshold signatures, Tendermint's precommit signing — relies on digital signature schemes (typically ECDSA or BLS) whose security rests on the hardness of the discrete-logarithm or elliptic-curve discrete-logarithm problem. A sufficiently large fault-tolerant quantum computer running Shor's algorithm breaks both. This isn't an abstract, decades-off concern to cryptographers — NIST finalized its first post-quantum signature standards in 2024, and migration timelines for critical infrastructure are already being planned around a "harvest now, decrypt later" threat model, where adversaries record signed messages today specifically to forge or replay them once quantum hardware matures.

The open problem isn't simply "swap in a post-quantum signature scheme" — it's that post-quantum signatures (lattice-based schemes like Dilithium, hash-based schemes like SPHINCS+) are substantially larger and slower to verify than ECDSA or BLS. HotStuff's entire efficiency argument in article 6.3 rested on constant-size threshold signatures collapsing an O(n²) view-change into O(n); most post-quantum signature schemes don't yet have a mature, efficient threshold-signature analogue with the same collapsing property. Rebuilding Byzantine consensus's communication-complexity wins from Phase 7 on a post-quantum signature foundation, without regressing back toward PBFT-era O(n²) costs, remains active, unsettled research.

Consensus for AI training coordination

Distributed AI training — the gradient-synchronization and parameter-server coordination underlying every large model trained since the mid-2010s — has historically avoided classical Byzantine consensus almost entirely, relying instead on simpler, weaker coordination (all-reduce collectives, parameter-server last-writer-wins) that assumes a mostly-trusted, mostly-reliable cluster. That assumption is starting to break in two directions at once: training clusters are growing large enough that partial hardware failures during a multi-week run are now a routine, expected event (echoing article 1.1's opening thesis, now arriving in a domain that hadn't needed to care), and federated and decentralized training setups — where training nodes belong to different, mutually-untrusting organizations — genuinely need Byzantine-robust gradient aggregation, not just crash-fault-tolerant checkpointing.

The open problem is that classical Byzantine consensus (this series' entire Phase 6) was designed for agreeing on a single, exact value or an ordered log — a fundamentally different problem from robustly aggregating millions of noisy, high-dimensional gradient vectors where a small amount of statistical corruption is tolerable and exact agreement is neither necessary nor efficient to achieve. Byzantine-robust gradient aggregation (trimmed-mean, median-of-means, and related statistical-robustness techniques) is a genuinely different research thread from log-replication consensus, and reconciling the two — getting the crash-tolerance and reconfiguration machinery this series covered in Phase 8-9 to work efficiently at AI-training's scale and message rate — remains largely unsolved outside of research prototypes.

Verifiable consensus without trusted hardware

Several production Byzantine-fault-tolerant systems (particularly in permissioned-blockchain and confidential-computing contexts) sidestep part of the Byzantine problem by assuming trusted execution environments — Intel SGX, AMD SEV — that let a node cryptographically prove it ran the correct code, reducing the effective fault model in ways that make consensus cheaper. This is a real, deployed technique, but it isn't a solved problem so much as a traded one: TEEs have their own history of side-channel vulnerabilities (Spectre-class attacks, cache-timing leaks) that have repeatedly undermined the exact isolation guarantee the consensus protocol was relying on, and depending on TEE vendor hardware reintroduces a form of centralized trust that Byzantine fault tolerance was supposed to eliminate in the first place.

The open research question is whether verifiable computation techniques that don't depend on trusted hardware at all — zero-knowledge proof systems, verifiable computation more broadly — can be made efficient enough to replace TEE-based shortcuts in Byzantine consensus, letting a node prove correct execution of complex logic without a hardware root of trust. Current zero-knowledge proof generation remains computationally expensive relative to the communication-round costs this series has spent nine phases optimizing (PBFT's O(n²), HotStuff's O(n), Flexible Paxos's quorum-overlap relaxation in article 7.2) — meaning any TEE-free verifiable-consensus scheme today typically trades network efficiency for proof-generation cost, not eliminating the trade-off, just relocating it.

The decentralization-versus-latency tension, still unresolved

This is the least novel and most persistent open problem in the whole series — every phase from article 1.3's CAP theorem through article 9.5's WAN read-optimization through 10.3's Meerkat has, in one form or another, been managing the same fundamental tension rather than resolving it: wider geographic and organizational decentralization (more independent parties, more geographically spread replicas, weaker trust assumptions) directly increases the physical and cryptographic cost of reaching agreement, while lower latency demands push toward fewer round trips, fewer participants, and stronger trust assumptions. QuePaxa (10.2) and Meerkat (10.3) both represent genuine, real progress on this tension specifically for the WAN case — but neither eliminates it; QuePaxa's fast path still degrades under sufficiently adversarial conditions, and Meerkat is explicitly scoped to small control-plane state rather than general-purpose data specifically because the tension gets worse, not better, as data volume grows.

The honest, series-closing observation article 10.1's framework prepared readers to make is this: no algorithm covered across sixty planned articles eliminates the CAP/PACELC trade-off articles 1.3 and 1.4 established in Phase 1 — every subsequent phase has been a set of increasingly sophisticated ways of choosing where along that trade-off to sit, and how cheaply to sit there, not a way of escaping the trade-off itself. That is the single most durable lesson underneath the entire sixty-article map, and it is exactly why Phase 11 turns next toward genuinely new application domains (blockchain, edge/IoT) rather than yet another algorithm claiming to have "solved" consensus once and for all.

FAQ

Should production systems worry about post-quantum consensus today?

For most systems, not urgently — but for anything with a multi-decade data-retention or infrastructure-longevity requirement, migration planning should start now given NIST's 2024 standardization and realistic quantum-hardware timelines; "harvest now, decrypt later" makes today's signed messages a future liability even before quantum hardware exists.

Is Byzantine-robust gradient aggregation the same field as Byzantine consensus?

Related but distinct — both share the "some participants may be malicious" threat model from article 6.1, but robust aggregation tolerates approximate, statistical correctness where classical consensus (Phase 4-7) demands exact agreement; the two research communities have historically been fairly separate, and bridging them is itself part of the open problem.

Does any current system solve the decentralization-latency tension?

No — every system this series covered makes a specific, deliberate choice along that trade-off (Meerkat: fewer keys, more replicas, WAN-tolerant; CockroachDB/Spanner from Phase 9: more data, region-scoped locality, tighter trust) rather than eliminating the underlying tension, which is the article's central point.

Takeaways

• Post-quantum Byzantine consensus is an open, active research problem because post-quantum signature schemes lack the mature, efficient threshold-signature analogues HotStuff's O(n) efficiency (article 6.3) depended on.
• AI training coordination needs a different kind of Byzantine robustness — statistical, gradient-aggregation robustness rather than exact log agreement — and reconciling it with this series' crash-tolerance machinery remains largely unsolved outside research prototypes.
• TEE-free verifiable consensus (zero-knowledge proofs replacing trusted hardware) trades network-round efficiency for proof-generation cost rather than eliminating the trade-off.
• The decentralization-versus-latency tension from article 1.3's CAP theorem is the one constant no algorithm across sixty articles has eliminated — every phase has been progressively cheaper ways of choosing a point on that trade-off, not an escape from it.
• This closing honesty — naming what remains unsolved rather than claiming false resolution — is the same discipline article 10.1 asked readers to bring to every paper they read.

References & further reading

• cvam.sight — Consensus 1.3: The CAP Theorem, Properly — the foundational trade-off every open problem in this article still traces back to.
• cvam.sight — Consensus 6.1: The Byzantine Generals Problem — the fault model post-quantum and AI-training consensus both have to extend or adapt.
• cvam.sight — Consensus 10.3: Meerkat — the clearest real-world example of choosing, not escaping, the decentralization-latency trade-off.