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.
At a glance:
| Barrier | Adversary picture | What changes the conclusion |
|---|---|---|
| CAP | split the replicas or resources into two plausible worlds | a non-faulty majority, or bounded timing assumptions |
| Byzantine split brain | split the honest parties into two sides, with Byzantine parties bridging the views | an honest $>2/3$ majority |
| Unauthenticated Byzantine agreement | simulate parties from another execution | non-simulatable identities, such as a PKI |
| Non-equivocation or transferability alone | give the protocol one property but not the other | a mechanism that provides both properties together |
| Rollback attacks | erase the memory that would have carried safety forward | persistent state, or the usual $3f+1$ threshold |
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 that can claw back in-flight messages from newly corrupted parties. The adversary waits to see who sends a message to the party it wants to isolate, corrupts that sender, and then claws back the still-undelivered message. This claw-back ability is the mathematical property that makes the lower bound go through.
The takeaway is that subquadratic agreement requires both randomization and a weaker adversary.
At a glance:
| Lower bound | Adversary recipe | Moral |
|---|---|---|
| Dolev-Reischuk | isolate one party | agreement needs enough messages to reach everyone |
| DR for Crusader Broadcast | reuse isolation for a weaker broadcast task | the same isolation argument applies beyond agreement |
| DR for strongly adaptive randomized agreement | corrupt senders after seeing them and claw back in-flight messages | randomness is not enough against adaptive with claw-back power |
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.
At a glance:
| Setting | What the adversary preserves | Resulting barrier |
|---|---|---|
| Synchronous consensus | an uncommitted configuration | $t+1$ rounds |
| Asynchronous consensus | an uncommitted configuration | an infinite execution |
| Mobile crash in synchrony | a pivotal configuration | infinite executions again |
| Early stopping | a pair of AS-FFD configurations | even good executions may need two more rounds |
| Simultaneous agreement | disagreement about which side of a time threshold was crossed | the $t+1$ barrier returns |
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. It is not one lower bound, but a collection of tight bounds across several regimes.
A related post, The round complexity of Reliable Broadcast, asks the same kind of question for reliable broadcast, measuring asynchrony by causal message chains rather than real time. There the clean split is between authenticated and unauthenticated settings: two-round good-case reliable broadcast is possible at $n\geq 3f+1$ with a PKI, while without a PKI the same good case needs $n\geq 4f$.
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.
At a glance:
| Setting | Best latency / tradeoff | What changes it |
|---|---|---|
| Authenticated async reliable broadcast | tight 2-round good case | this is reliable broadcast, not partial-synchronous BFT SMR |
| Unauthenticated reliable broadcast | 2-round good case iff $n\geq 4f$; one-round bad-case catch-up for $f\geq 3$ needs $n\geq 5f-1$ | signatures reduce the threshold to $n\geq 3f+1$ |
| Partial synchrony, $n\leq 5f-2$ | at least 3 good-case rounds | more validators, stronger timing, or a weaker target |
| Partial synchrony, $n\geq 5f-1$ | tight 2-round good case | dropping below $5f-1$ brings back the 3-round lower bound |
| Synchrony, $0<f<n/3$ | tight $2\delta$ | at $f=n/3$ the bound jumps to $\Delta+\delta$ |
| Synchrony, $f=n/3$ | tight $\Delta+\delta$ | below this threshold, two actual-delay rounds suffice |
| Synchrony, $n/3<f<n/2$ | tight $\Delta+\delta$ with synchronized start; tight $\Delta+1.5\delta$ with unsynchronized start | clock synchronization changes the exact optimum |
| Synchrony, $n/2\leq f<n$ | known lower bound $\lfloor n/(n-f)\rfloor\Delta$ and $O(n/(n-f))\Delta$ upper bound | reducing the fault fraction moves back to the tight $f<n/2$ regimes |
| Rotating leaders | single-slot responsive rotation needs $2\Delta-O(\delta)$ and is matched by $2\Delta+O(\delta)$ | stable leaders or pipelining change the latency target |
| Fault-tolerant responsive fast path | responsive $O(\delta)$ commit forces synchronous fallback at least $2\Delta-O(\delta)$ | a zero-fault optimistic path avoids this tradeoff |
| Zero-fault responsive fast path | $\Delta$ synchronous latency is possible | the optimistic condition no longer tolerates even one fault |
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 5t-6$ and $t\geq 4$, 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: once censorship resistance is paid for, hiding, simultaneous binding, and last-look protection can be added under synchrony with the same two extra rounds.
At a glance:
| Property | Bound or tight point | What changes the conclusion |
|---|---|---|
| Honest input validity, synchrony | impossible for $n\leq \max(3,m)f$ with $m$ input values | above the threshold, gradecast reduces the problem to external validity |
| Honest input validity, asynchrony | impossible for $n\leq (m+1)f$ | above the threshold, reliable broadcast plus external validity is enough |
| Honest-input-or-default validity | no stronger lower bound than ordinary consensus | allowing $\bot$ lets the property reduce back to external validity |
| Majority / $k$-advantaged validity | $2f$-advantaged validity is impossible in asynchrony for any $n/f$, even binary | $2f+1$-advantaged validity is achievable |
| Censorship resistance in partial synchrony | at least 5 good-case rounds for $n\leq 5t-6$ and $t\geq 4$ | ordinary leader-based BFT can stop at 3; separating input holder $I$ from expediter $E$ costs two rounds |
| CR + SCQ + hiding + simultaneous binding + accountable last look | under synchrony and $n\geq 3f+1$, any BFT protocol can be augmented with two extra rounds | the three market protections are needed together: hiding, simultaneous binding, and last-look protection |
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.
At a glance:
| Object being protected | Adversary goal | Lower-bound shape |
|---|---|---|
| Agreement value | make honest parties decide differently | split worlds and pivots |
| VSS or MPC secret | learn before reconstruction is safe | privacy hybrids |
| Stored secret key | keep availability and privacy through partitions | SAP-style CAP tradeoff |
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.
One-line takeaway: safety says old decisions cannot conflict; liveness must also show that some future leader can still collect enough usable evidence to make progress.
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.
At a glance:
| Technique | Adversary move | Where to read |
|---|---|---|
| Split brain | make two sides see different legal executions | CAP, DLS |
| Simulation | make Byzantine parties imitate another world | FLM, Crusader Agreement |
| Isolation | keep one party below the evidence threshold | Dolev-Reischuk, strong adaptivity |
| Bivalence and pivots | move the critical difference forward | FLP model, synchronous $t+1$, early stopping |
| Validity worlds | force 0 in one world and 1 in another | good-case latency, three-round BFT |
| Privacy hybrids | change one secret or share at a time | asynchronous MPC, SAP |
Reading Map
For fault thresholds, read:
- The CAP theorem for partial synchrony
- State Machine Replication for Two Servers and One Omission Failure is Impossible
- In between Crash and Omission failures
- Blockchain Resource Pools and a CAP-esque Impossibility Result
- Byzantine Agreement is impossible for $n\leq 3f$ under partial synchrony
- Byzantine Agreement is Impossible for $n\leq 3f$ if the Adversary can Simulate
- Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$
- Neither Non-equivocation nor Transferability alone is enough
- $3f+1$ is needed in Partial Synchrony even against a Rollback adversary
For communication lower bounds, read:
- The Dolev and Reischuk Lower Bound
- A new Dolev-Reischuk style Lower Bound
- Agreement against strongly adaptive adversaries needs quadratic communication
For rounds and infinite executions, read:
- Consensus Lower Bounds via Uncommitted Configurations
- Synchronous Consensus Lower Bound via Uncommitted Configurations
- The FLP Impossibility
- Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Has Infinite Executions
- Early Stopping, Same but Different
- Synchronized Clocks, Fixed View Schedules, and Simultaneous Agreement
For good case latency, read:
- Good-case Latency of Byzantine Broadcast: a Complete Categorization
- The round complexity of Reliable Broadcast
- Good-case Latency of Byzantine Broadcast: the Synchronous Case
- Good-case Latency of Rotating Leader Synchronous BFT
- Why BFT Needs Three Rounds
- On the Optimality of Optimistic Responsiveness
For validity and censorship resistance, read:
For privacy and secret state, read:
- Asynchronous Fault Tolerant Computation with Optimal Resilience
- The SAP theorem for storing secret keys
For liveness attacks, read:
For classic external papers, read:
- Dwork, Lynch, Stockmeyer: Consensus in the Presence of Partial Synchrony
- Fischer, Lynch, Paterson: Impossibility of Distributed Consensus with One Faulty Process
- Fischer, Lynch, Merritt: Easy Impossibility Proofs for Distributed Consensus Problems
- Dolev and Reischuk: Bounds on Information Exchange for Byzantine Agreement
- Ben-Or, Kelmer, Rabin: Asynchronous Secure Computations with Optimal Resilience
- Good-case Latency of Byzantine Broadcast: A Complete Categorization