In this series of three posts, we discuss two of the most important consensus lower bounds:
 Lamport, Fischer [1982]: any protocol solving consensus in the synchronous model that is resilient to $t$ crash failures must have an execution with at least $t+1$ rounds.
 Fischer, Lynch, and Patterson [1983, 1985]: any protocol solving consensus in the asynchronous model that is resilient to even one crash failure must have an infinite execution.
The modern interpretation of these lower bounds is the following:
 Bad news: Without using randomness, asynchronous consensus is impossible, and synchronous consensus is slow.
 Good news: With randomization, consensus (both in synchrony and in asynchrony) is possible in a constant expected number of rounds. Randomness does not circumvent the lower bounds; it just reduces the probability of bad events implied by the lower bounds. In synchrony, the probability of slow executions can be made exponentially small. In asynchrony, termination happens almost surely. Formally, the probability measure of the complement of the event of terminating in some finite number of rounds is zero.
The plan: three posts

In this first post, we provide key definitions and prove an important Lemma about having some initial uncommitted configuration. This lemma shows that any consensus protocol has some initial input where the the adversary has control over the decision value (it can cause it to be either 0 or 1). This lemma will then be used in both lower bounds.

In the second post, we use the approach of Aguilera and Toueg [1999] to show that any protocol solving consensus in the synchronous model that is resilient to $t$ crash failures must have an execution with at least $t+1$ rounds. The proof uses the definitions and the lemma in this post.

In the third post, we show the celebrated Fischer, Lynch, and Patterson [1985] result that any protocol solving consensus in the asynchronous model that is resilient to even one crash failure must have an infinite execution. The proof uses the same definitions and the lemma in this post.
Definitions
We assume $n$ parties. Each party is a state machine that has some initial input $\in {0,1}$. The state machine has a special decide action that irrevocably sets its decision $\in {0,1}$.
We say that a protocol $\mathcal{P}$ solves agreement against $t$ crash failures if in any execution with at most $t$ crash failures:
 Termination: all nonfaulty parties eventually decide.
 Agreement: all nonfaulty parties decide on the same value.
 Validity: if all nonfaulty parties have the same input value, then this is the decision value.
Given, a protocol $\mathcal{P}$, a configuration of a system is just the state of all the parties and the set of all pending, undelivered messages. More formally, a configuration $C$ is a vector of state machines and a set $C_M$ of pending messages. We say that $e\in C_M$ is a pending message and $e=(m,p)$ if the configuration $C$ has a pending message $m$ sent to a party $p$ that party $p$ did not receive yet.
The goal of a protocol $\mathcal{P}$ is to reach a configuration where all nonfaulty parties decide, despite the adversary’s control of the asynchrony and ability to corrupt parties. The magic moment of any consensus protocol is when a protocol reaches a committed configuration. This is a configuration where no matter what the adversary does from this point onwards, the eventual decision value is already fixed. Note that event of a system when its configuration becomes committed is an event that is only externally observable. There is no local indication of this event and this can happen much before any party actually decides!
We choose to use new names to these definitions, which we feel provide a more intuitive and modern viewpoint. The classical names are bivalent configuration for uncommitted configuration and univalent configuration for committed configuration.
The following formal definitions are crucial:

We write $C \rightarrow C’$: If in configuration $C$ there is a pending message $e$ (or all undelivered messages $E$ in the synchronous model) such that configuration $C$ changes to configuration $C’$ by delivering $e$ (or delivering all $E$ in the synchronous model). When a pending message $e=(m,p)$ is delivered, then party $p$ receives message $m$ and locally processes it fully according to $\mathcal{P}$. Since the system is asynchronous, the full local processing will assume that all timers expire (for example, if $\mathcal{P}$ instructs $p$ to wait for 2 hours, then we wait for this timer to expire). So the difference between $C$ and $C’$ is: (1) in the state of party $p$ after fully completing the processing of $e$; and (2) in the sent of pending messages of $C’$, $e$ is removed, and may contain new messages that are sent by $p$ to other parties due to the processing of $m$.
 We write $C \rightsquigarrow C’$: If there exists a sequence $C = C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_k=C’$ ($\rightsquigarrow$ is the transitive closure of $\rightarrow$).

$C$ is a deciding configuration: if all nonfaulty parties have decided in $C$. We say that $C$ is 1deciding if the common decision value is 1, and similarly that $C$ is 0deciding if the decision is 0.
Note that it’s easy to check if a configuration is deciding  just look at the local state of each nonfaulty party.

$C$ is an uncommitted configuration: if it has a future 0deciding configuration and a future 1deciding configuration. There exists $C \rightsquigarrow D_0$ and $C \rightsquigarrow D_1$ such that $D_0$ is 0deciding and $D_1$ is 1deciding.
Said differently, an uncommitted configuration is a configuration where the adversary still has control over the decision value. There are some adversary actions (crash events, message delivery order) that will cause the parties to decide 0 and some adversary actions that will cause the parties to decide 1.
An uncommitted configuration is a state of a system as a whole, not something that can be observed locally. Note that there is no simple way to know if a configuration is uncommitted. It requires examining all the possible future configurations (all possible adversary actions).

$C$ is a committed configuration: if every future deciding configuration $D$ (such that $C \rightsquigarrow D$) is deciding on the same value. We say that $C$ is 1committed if every future ends in a 1deciding configuration, and similarly that $C$ is 0committed if every future ends in a 0deciding configuration.
Said differently, a committed configuration is a configuration where the adversary has no control over the decision value. When a configuration is committed to $v$, no matter what the adversary does, the decision value will eventually be $v$.
Note that there is no simple way to know if a configuration is committed or uncommitted. In particular, there is no local indication in the configuration, and it may well be that no party knows that the configuration is committed.
The existence of an initial uncommitted configuration
With the new definitions, one way to state the validity property is: if all nonfaulty parties have the same input $b$ then that initial configuration must be $b$committed.
So perhaps all initial configurations are committed? The following lemma shows that this is not the case: every protocol that can tolerate even one crash failure must have some initial configuration that is uncommitted.
Lemma 1 (Lemma 2 of FLP85): If $\mathcal{P}$ solves agreement against at least one crash failure, then $\mathcal{P}$ has an initial uncommitted configuration.
A recurring proof pattern for showing the existence of an uncommitted configuration will appear many times in these three posts. We start by stating it in an abstract manner:
 Proof by contradiction: assume all configurations are either 1committed or 0committed.
 Define some notion of adjacency. Find two adjacent configurations $C$ and $C’$ such that $C$ is 1committed and $C’$ is 0committed.
 Reach a contradiction due to an indistinguishability argument between the two adjacent configuration $C$ and $C’$. The adjacency allows the adversary to cause indistinguishability via crashing of just one party.
Proof of the Lemma 1 fits this pattern perfectly:
 Seeking a contradiction, assume there is no initial configuration that is uncommitted. So all initial configurations are either 1committed or 0committed.
 Define two initial configurations as $i$adjacent if the initial value of all parties other than party $i$ are the same. Consider the sequence (or path) of $n+1$ adjacent initial configurations: $(1,\dots,1),(0,1,\dots,1),(0,0,1\dots,1),\dots,(0,\dots,0)$. Clearly, the leftmost is 1committed and the rightmost is 0committed. Obviously, there must be some party $i$ such that the two $i$adjacent configurations $C,C’$ are 0committed and 1committed, respectively.
 Now consider in both worlds $C$ and $C’$ the case where party $i$ crashes right at the start of the protocol. These two worlds are indistinguishable for all nonfaulty parties, which, therefore, must decide the same value. This is a contradiction.
This proves that any protocol $\mathcal{P}$ must have some initial uncommitted configuration. The next two posts will use the existence of an initial uncommitted configuration and extend it to more rounds!
Proof by example for n=3: Consider the 4 initial configurations $(1,1,1), (0,1,1),(0,0,1),(0,0,0)$. By validity, configuration $(1,1,1)$ must be 1committed and configuration $(0,0,0)$ must be 0committed. Seeking a contradiction, lets assume none of the 4 initial configurations is uncommitted. So both $(0,1,1)$ and $(0,0,1)$ are committed. Since all 4 initial configurations are committed there must be two adjacent configurations that are committed to different values. W.l.o.g. assume that $(0,1,1)$ is 1committed and $(0,0,1)$ is 0committed. Now suppose that in both configurations, party 2 crashes right at the start of the protocol. Clearly both configurations look like $(1,CRASH,0)$. So both worlds must decide the same, but this is a contradiction because one is 1committed and the other is 0committed.
Acknowledgment. We would like to thank Kartik for helpful feedback on this post.
Please leave comments on Twitter