# Understanding “Impossibility of Distributed Consensus with One Faulty Process”

By [imlearning.eth](https://paragraph.com/@imlearning) · 2022-02-27

---

Consensus Protocol
==================

Let us start by integrating some unfamiliar definitions in this paper. By reading through these concepts, you should be able to grasp the big picture of how the consensus protocol works. I added some illustrations to further understand how these concepts are linked together to form a protocol.

![FIGURE 1. Concept of process, and message system.](https://storage.googleapis.com/papyrus_images/fc39ed2f85e23972ae9251754510d7999984449ef92592267f0eb4b868fc8e06.png)

FIGURE 1. Concept of process, and message system.

![FIGURE 2. Concept of the configuration and sequence.](https://storage.googleapis.com/papyrus_images/648f73f557e7e17ff201c9a1fce7799a521ddd97caddd9f43f1a933184a70146.png)

FIGURE 2. Concept of the configuration and sequence.

*   **_consensus protocol_**: denoted by _P_ (capital). This paper assumes that _P_ is an asynchronous system of N processes (N ≥ 2).
    
*   **_process_**: denoted by _p_ (lower case). A process can be understood as a node, which has its internal storage, and state that is determined by inputs and a _transition function_. See Figure 1 below.
    
*   **_input register_**: process _p_ has one input register _x\_p_ with values either of b or 0 or 1.
    
*   **_output register_**: process _p_ has one output register _y\_p_ with values either of b or 0 or 1. process _p_ has its _y\_p_ value as b initially, but as soon as it becomes 0 or 1, it cannot be changed (thus, _output register_ is “write once”).
    
*   **_internal state_**: The values in _x\_p_ and _y\_p_ comprise the _internal state_.
    
*   **_initial state_**: initial state has its _y\_p_ value “b” but _x\_p_ value can vary.
    
*   **_decision state_**: a state in which _y\_p_ has a value either of 0 or 1. once a process becomes the _decision state_, _y\_p_ cannot be changed anymore.
    
*   **_transition function_**: transition function determines _y\_p_ (output). but cannot change _y\_p_ anymore once _p_ becomes _decision state_.
    
*   **_message_**: a _message_ is a pair (_p_, _m_), where _p_ is the destination process and _m_ is a message value from a fixed universe _M_.
    
*   **_message buffer_**: a FIFO queue of _messages_ that have been sent but not yet received. _message buffer_ supports two operations:
    
    1.  send(_p_, _m_): send message _m_ to the process _p_. place (_p_, _m_) in the message buffer.
        
    2.  receive(_p_): deletes some message (_p_, _m_) from the _buffer_ and returns _m_ OR returns null and leaves the buffer unchanged.
        
*   **_configuration_**: _configuration_ consists of 1. _internal state_ of each process and 2. contents of the _message buffer_. See Figure 2.
    
*   **_initial configuration_**: a _configuration_ in which each process starts at an _initial state_ and the _message buffer_ is empty.
    
*   **_step_**: a _step_ takes one _configuration_ C to another _configuration_ C’.
    
*   **_event_**: event is denoted by _e_. _e_ = (_p_, _m_), which means a receipt of m by _p_. e(C) denotes the _resulting configuration_, and we say that _e_ can be applied to C.
    
*   **_sequence_**: _sequence_ σ is a set of multiple _events_.
    
*   **_schedule_**: finite or infinite _sequence_ σ that can be applied starting from C.
    
*   **_resulting configuration_**: σ(C).
    
*   **_reachable_**: if σ(C), σ(C) is _reachable_ from C.
    
*   **_accessible_**: a configuration _reachable_ from some _initial configuration_ is _accessible_.
    

So, with the background knowledge above, we are going to prove that:

> Theorem: There is always a sequence of events in an asynchronous distributed system such that the group of processes never reach consensus

by showing that there is a case in which protocol remains forever indecisive.

Lemma 1
-------

> LEMMA 1. **Commutativity** property of schedules. Suppose that from some configuration C, the schedules σ1, σ2 lead to configurations C1, C2, respectively. If the sets of processes taking steps in σ1 and σ2, respectively, are disjoint, then σ2 can be applied to C1 and σ1 can be applied to C2, and both lead to the same configuration C3.
> 
> **i.e., σ1(σ2(C)) = σ2(σ1(C)), if the sets of processes taking steps in σ1 and σ2 are disjoint.**

PROOF: The result follows at once from the system definition, since σ1 and σ2 do not interact.

![Source: Impossibility of Distributed Consensus with One Faulty Process, p.377](https://storage.googleapis.com/papyrus_images/0b76c396f09ff0dfe9585fd59e73fa61d03b0017da84586a2fdb3543adb9cfe6.png)

Source: Impossibility of Distributed Consensus with One Faulty Process, p.377

So, LEMMA 1 proves that **schedules are applicable without considering an order, resulting in the same resulting configuration.** This “commutativity” property of schedule is used to prove Lemma 3.

Lemma 2
-------

We need to understand what the “valency” is before we step into the proof of lemma 2. Here is a table for the grasp.

*   **univalent**: if all reachable configurations have decision value v (thus in a decision state), we just call the configuration univalent.
    
*   **0-valent**: univalent, with all of the reachable configurations having decision value 0.
    
*   **1-valent**: univalent, with all of the reachable configurations having decision value 1.
    
*   **bivalent**: if all reachable configurations do not have the same decision value v, we just call the configuration bivalent.
    

> LEMMA 2. Consensus protocol _P_ has a **bivalent initial configuration**.

PROOF: We use contrary proof. Assume that _P_ must have only univalent initial configurations. So, _P_ must have both 0-valent and 1-valent initial configurations.

Let us call two initial configurations _adjacent_ if they differ only in the initial value _x\_p_ of a **single process _p_**.

**(REMINDER**: _initial configuration_: a _configuration_ in which each process starts at an _initial state_ and the _message buffer_ is empty. _initial state_: initial state has its _y\_p_ value “b” but _x\_p_ value can vary.**)**

If we list all the possible initial configurations, there must be two adjacent initial configurations, 0-valent and 1-valent respectively, and the only difference between them is the x\_p value of a single process _p_.

Now we consider applying sequence σ to both initial configuration n and n+1 assuming that the process _p_ does not take any step.

![FIGURE 3. initial configurations and contradiction.](https://storage.googleapis.com/papyrus_images/00099300ba89838160cb6c1c422ce86b34314ba9c614bdc2dd0ceb45ed09eaec.png)

FIGURE 3. initial configurations and contradiction.

If sequence σ can be applied to initial configuration n, then it is also applicable to initial configuration n+1 because they are identical except the x\_p value of a single process _p_, and now _p_ is halted by the assumption. σ(config n) = σ(config n+1). If the decision value of configuration C is 1, then config n is bivalent. Reversely, if the decision value of configuration is 0, then config n+1 is bivalent. This contradicts the assumed nonexistence of a bivalent initial configuration. End of proof.

So, in short, LEMMA 2 proves that **there exists a bivalent initial configuration.**

Lemma 3
-------

> LEMMA 3. Let C be a bivalent configuration of P, and let e = (p, m) be an event that is applicable to C. Let **_C_** be the set of configurations reachable from C without applying e, and let **_D_** = e(**_C_**) = {e(E) | E ∈ **_C_** and e is applicable to E}. Then, **_D_** contains a bivalent configuration.

PROOF: Since e is applicable to C, then by the definition of C and the fact that messages can be delayed arbitrarily (by LEMMA 1), e is applicable to every E ∈ **_C_**.

We also use contrary proof here again. Now assume that **_D_** contains no bivalent configurations, so every configuration F ∈ **_D_** is univalent.

![FIGURE 4. Reachable configurations from C.](https://storage.googleapis.com/papyrus_images/bf47a54ed27354d665839b6210432897dcc4293ef0b30c276a55b645b04c53be.png)

FIGURE 4. Reachable configurations from C.

If F is a configuration reachable from E, then F is also either 0-valent or 1-valent since D contains no bivalent configuration by the assumption. As _e_ is applicable to every E ∈ C, by an easy induction, there exist E\_n and E\_n+1 such that F\_n = e(E\_n) and F\_n+1 = e(E\_n+1).

![FIGURE 5. Case 1, when p’ ≠ p.](https://storage.googleapis.com/papyrus_images/ad3f85181a09ae0e7dbb9fa2a4191bc81cb06f001e8e33b78bfa894ff6c7804f.png)

FIGURE 5. Case 1, when p’ ≠ p.

Let event e = (p, m) and e’ = (p’, m’).

**CASE 1**: If p’ ≠ p, then F\_n+1 = e’(F\_n) by LEMMA 1. This is impossible, since any successor of a 0-valent configuration is 0-valent. i.e., F\_n(0-valent configuration) → F\_n+1(1-valent configuration) is impossible.

**CASE 2**: If p’ = p, then consider any finite deciding schedule from E\_n in which _p_ takes no steps:

![FIGURE 6. Case 2, when p’ = p.](https://storage.googleapis.com/papyrus_images/9faa7f8b6be9cc86931a0c23534f9867f41f352fdb2718ff0d8377054a22315c.png)

FIGURE 6. Case 2, when p’ = p.

Let σ the schedule, and let configuration A = σ(E\_n). By LEMMA 1, σ is applicable to F\_n and F\_n+1, and it leads to 0-valent configuration G\_n = σ(F\_n) and 1-valent G\_n+1 = σ(F\_n+1). Also by LEMMA 1, e(A) = G\_n and e(e’(A)) = G\_n+1. So, configuration A is bivalent, but this is impossible since the schedule to A is deciding by the assumption. So A must be univalent. In this case, we reach a contradiction. End of proof.

So, LEMMA 3 proves that **there exists a bivalent configuration that can be reached from the bivalent configuration.**

Integration
-----------

Let us integrate the lemmas we have just proved so far and build a conclusion.

> (LEMMA 1: schedules are applicable without considering an order, resulting in the same resulting configuration. i.e., commutativity property of schedules.)
> 
> LEMMA 2: there exists a bivalent initial configuration.
> 
> LEMMA 3: there exists a bivalent configuration that can be reached from the bivalent configuration, proved with LEMMA 1.

Considering LEMMA 2 and LEMMA 3, we can finally prove that **there is a case in which protocol remains forever indecisive.**

If there is a schedule that runs from bivalent configuration (whose existence is proved by LEMMA 2 and 3) to a univalent configuration, there must be a some single step that goes from a bivalent to a univalent configuration. Such a step determines the eventual decision value. It is always possible to run the asynchronous system in a way that avoids such steps by failing single process.

### References:

[https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf](https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf)

[https://www.cs.purdue.edu/homes/peugster/classes/CS505Spring09/10-Consensus.pdf](https://www.cs.purdue.edu/homes/peugster/classes/CS505Spring09/10-Consensus.pdf)

[![]({{DOMAIN}}/editor/youtube/play.png)](https://www.youtube.com/watch?v=KpJ6pENjrtE)

**FEEDBACK IS ALWAYS WELCOMED! Please DM(@ysjlitt twitter) me if you find any errors in this article.**

---

*Originally published on [imlearning.eth](https://paragraph.com/@imlearning/understanding-impossibility-of-distributed-consensus-with-one-faulty-process)*