Chapter: Lower Bounds

This post is a map of the lower-bound posts on Decentralized Thoughts. The Start Here page already lists many of these results by topic, and the lowerbound tag lists the posts themselves. Here we turn that list into a chapter: first the main fault-threshold barriers, then communication, round complexity, latency, validity, privacy, and liveness.

In distributed computing, an upper bound is often a condition and a protocol for the honest parties. Under that condition, the protocol lets the honest parties satisfy the target property against any adversary. A useful way to think about lower bounds is this:

A lower bound is a condition and a protocol for the adversary. Under that condition, the protocol lets the adversary violate the target property of any honest-party protocol.

This symmetry is the beauty of lower bounds. They are not only abstract statements about what is impossible; they often give an explicit adversarial strategy. A proof is often a recipe: assume all but one of the desired properties, then show that the adversary can break the last one.

Fault Thresholds

The most basic question is how many faults a system can tolerate.

The first answer is the familiar majority barrier. In state machine replication, a 50-50 split forces a choice: keep safety, or keep liveness, but not both. This is the message of the CAP theorem for partial synchrony. The same majority barrier appears even in lock step synchrony with omission faults: State Machine Replication for Two Servers and One Omission Failure is Impossible. The post In between Crash and Omission failures sharpens this picture by looking at weaker omission models.

There is also a permissionless version of the same obstruction: Blockchain Resource Pools and a CAP-esque Impossibility Result. The language is different, but the adversary is again exploiting a split in available resources.

The next barrier concerns Byzantine faults. In partial synchrony, Dwork, Lynch, and Stockmeyer showed that Byzantine agreement needs $n>3f$. The DT post Byzantine Agreement is impossible for $n\leq 3f$ under partial synchrony gives the split brain proof in blog form.

The unauthenticated version has the same threshold for a different reason, and the lower bound holds even in synchrony. The Fischer, Lynch, and Merritt simulation lower bound says that without a PKI, or more generally when the adversary can simulate parties, Byzantine agreement requires $n>3f$. See Byzantine Agreement is Impossible for $n\leq 3f$ if the Adversary can Simulate. The same simulation idea can be strengthened to rule out even Crusader Agreement with $\leq 1/3$ Error at $n\leq 3f$.

Cryptographic or hardware restrictions can help, but only if they give the right property. The post Neither Non-equivocation nor Transferability alone is enough explains why each property alone is insufficient for minority corruptions in asynchrony. In a related direction, TEEs without persistent state do not escape the Byzantine threshold in partial synchrony: $3f+1$ is needed in Partial Synchrony even against a Rollback adversary.

Communication

The next question is how many messages agreement needs.

The classic answer is the Dolev-Reischuk lower bound: deterministic Byzantine agreement needs quadratically many messages in the worst case. The DT post The Dolev and Reischuk Lower Bound gives the main isolation argument. If too few messages are sent, the adversary can isolate a party and make it unable to tell which decision is required.

The same isolation template can be reused for other primitives. In A new Dolev-Reischuk style Lower Bound, the target is Byzantine Crusader Broadcast rather than agreement.

Randomization does not automatically remove this barrier. The post Agreement against strongly adaptive adversaries needs quadratic communication extends the message lower bound to randomized protocols against a strongly adaptive omission adversary. The adversary waits to see who sends a message to the party it wants to isolate, corrupts that sender, and prevents that message from being delivered.

The takeaway is that subquadratic agreement requires both randomization and a weaker adversary.

Rounds and Infinite Executions

The next natural question is how many rounds agreement or other tasks need.

The introductory post is Consensus Lower Bounds via Uncommitted Configurations. It sets up the language of committed and uncommitted configurations (univalent and bivalent). A configuration is uncommitted when the adversary can force at least two futures with different decision values.

In synchrony, this gives the classic $t+1$ round lower bound: Synchronous Consensus Lower Bound via Uncommitted Configurations. Even with crash faults, an adversary can spend one crash per round and keep the execution uncommitted. Note that this $t+1$ round lower bound holds even for randomized protocols.

In asynchrony, the same idea gives FLP: The FLP Impossibility. The original paper is Fischer, Lynch, and Paterson. The real implication is that:

Every protocol solving consensus in asynchrony (even randomized ones) must have an infinite execution even against one crash fault.

This statement also implies the weaker statement that has been more commonly quoted:

Deterministic consensus in asynchrony is impossible even against one crash fault.

But note that the infinite execution statement is stronger: it applies to randomized protocols, and it applies to any protocol that solves consensus, not just deterministic ones.

The post Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Has Infinite Executions puts FLP and the Santoro-Widmayer mobile crash lower bound into one view. The proof tracks a pivot configuration and moves the pivot forward. The post also offers a simpler, more modern proof of the FLP theorem.

Finally, Early Stopping, Same but Different asks what happens when the actual number of failures is smaller than the maximum number the protocol tolerates. The lower bound is still a pivot argument, but now the question is how soon the protocol can decide in executions with few or no failures.

This is also the right place to read Synchronized Clocks, Fixed View Schedules, and Simultaneous Agreement. Trying to let a fixed view schedule jump early after a fast good case forces parties to agree not only on a value, but also on which side of a time threshold they decide. That is simultaneous agreement, and it has the same $t+1$ barrier.

Broadcast Round Complexity

Broadcast has its own round lower bounds. The round complexity of Reliable Broadcast asks how quickly reliable broadcast can terminate once we measure asynchrony by causal message chains rather than real time.

The clean split is between authenticated and unauthenticated settings. With a PKI, two-round good-case reliable broadcast is possible at $n\geq 3f+1$. Without a PKI, the same good case needs $n\geq 4f$, and this is tight: unauthenticated reliable broadcast at $n\leq 4f-1$ cannot have a two-round good case. The bad case has its own price: if the broadcaster is faulty, making all honest parties output one round after any honest party outputs runs into a $5f-2$ style barrier.

Good Case Latency

Good case latency lower bounds ask a more refined question:

If the leader is honest and the network is synchronous, how quickly can all honest parties decide?

The broad map is Good-case Latency of Byzantine Broadcast: a Complete Categorization, with the corresponding paper Good-case Latency of Byzantine Broadcast: A Complete Categorization. The post separates synchrony, partial synchrony, and asynchrony, and gives tight thresholds for two-round good-case protocols.

For synchrony, read Good-case Latency of Byzantine Broadcast: the Synchronous Case. The main theme is equivocation detection. Depending on the exact resilience regime, the best latency is not always an integer number of full delay bounds.

For rotating leaders in synchrony, read Good-case Latency of Rotating Leader Synchronous BFT. It explains why, when leaders rotate and propose responsively, a single slot cannot beat the $2\Delta$ barrier.

For partial synchrony, there is an especially important lower bound: Why BFT Needs Three Rounds. For $n\leq 5f-2$, a Byzantine broadcast protocol in partial synchrony needs at least three rounds in the good case. This is why PBFT, Tendermint, HotStuff, Casper FFG, and Simplex all have the proposal plus two voting round pattern at optimal resilience. Two-round good-case protocols need more validators, a different timing assumption, or a weaker target.

The related responsiveness lower bound is On the Optimality of Optimistic Responsiveness. Optimistic responsiveness is powerful, but it does not make the adversary’s view gap disappear for free.

Validity and Censorship Resistance

Many lower bounds become sharper once validity is made more explicit.

The starting point is What about Validity?. Classic validity is weak for blockchain protocols, where values are usually client requests or application states. External validity solves one problem: the protocol can check that a proposed value is valid without requiring all honest parties to start with the same input. Stronger validity notions, such as honest input validity or majority validity, create new lower bounds.

Censorship resistance changes the good case latency problem. In a traditional leader based BFT protocol, the leader both constructs the input and proposes it. Censorship resistance separates these roles: an input holder has the value, while an expediter drives the protocol. The post Latency cost of censorship resistance shows that this separation costs two rounds in partial synchrony. For $n\leq 5f-6$, a censorship resistant protocol cannot have good case latency below five rounds.

The natural follow up is Beyond censorship resistance: hiding, simultaneous binding, and accountable last look. That post is more about goals than lower bounds, but the lower bounds in this section explain why those goals need extra rounds or extra assumptions.

Privacy and Secret State

Privacy lower bounds are different from agreement lower bounds because the adversary is not only trying to split decisions. It is also trying to learn or expose a secret before the protocol has enough agreement about who is allowed to know it.

The post Asynchronous Fault Tolerant Computation with Optimal Resilience explains the Ben-Or, Kelmer, Rabin lower bound: asynchronous verifiable secret sharing with perfect security has a nonzero probability of nontermination when $n/4\leq f<n/3$. This is why perfectly secure asynchronous MPC has the familiar $n>4f$ threshold.

The post The SAP theorem for storing secret keys is the secret key analogue of CAP. If a system wants secret availability and secret privacy under partitions, it must pay with another assumption or give up one of the properties.

Liveness Attacks

Lower bounds are not always about agreement. Some are about progress.

Raft does not Guarantee Liveness in the face of Network Faults shows that omission faults can keep Raft from making progress. The issue is not safety; it is that the leader election and message pattern allow the adversary to prevent a stable leader from getting the messages it needs.

This is a useful reminder for partially synchronous BFT as well. A safety proof does not automatically give a liveness proof. In protocols like Simplex, Complex, Kuplex, and fixed view schedule variants, the liveness argument has to explain exactly why some future leader can form a valid proposal.

Proof Techniques

It is useful to read the posts not only by result, but also by technique.

Split brain. Partition the parties so that two sides see different legal executions. This is the core of CAP, DLS, and many partial synchrony threshold lower bounds.

Simulation. Let Byzantine parties imitate honest parties from other executions. This is the FLM technique and also appears in Crusader Agreement lower bounds.

Isolation. Keep one party from receiving enough messages. This is the Dolev-Reischuk template and its strongly adaptive variants.

Bivalence and pivots. Keep the execution uncommitted by moving one critical difference forward. This is the FLP line, the synchronous $t+1$ round lower bound, early stopping, and simultaneous agreement.

Validity worlds. Build one execution where validity forces value $0$ and another where validity forces value $1$, then connect them through a mixed execution. This is the proof style behind many good-case latency lower bounds.

Privacy hybrids. Change one party’s secret or one share at a time while preserving what the adversary can see. This is the natural language of privacy and secret state lower bounds.

Reading Map

For fault thresholds, read:

For communication lower bounds, read:

For rounds and infinite executions, read:

For broadcast round complexity, read:

The round complexity of Reliable Broadcast

For good case latency, read:

For validity and censorship resistance, read:

For privacy and secret state, read:

For liveness attacks, read:

Raft does not Guarantee Liveness in the face of Network Faults

For classic external papers, read:

Tags: consensus lowerbound