<p>It shows that there are no fault-tolerant deterministic algorithm. Quite a strong theoretical result, which forces designers to deal differently with fault-tolerance, some of which are synchronization and randomization. </p>

<p>Comment: In my opinion, synchronization is an additional assumption of the system that are hardly found in practical applications. </p>

<p>For references, check <a href="http://en.wikipedia.org/wiki/Consensus_%28computer_science%29#Applications_of_consensus_protocols">the Wikipedia link</a>. 
Check also this <a href="http://jsaia.wordpress.com/2009/08/21/consensus/">blog</a> for practical applications </p>

CC BY-SA 3.0
2012-12-07T01:30:18.490Z
Yes, I prefer randomization to synchronization. The environment in which distributed computing plays is very poor in the sense of asynchronization, unbounded delay, unexpected failure, and too much non-deterministic. As long as it is not perfect, why don't we use randomization, achieving some guarantees while avoiding too much complexity.
hengxin
CC BY-SA 3.0
2012-12-07T01:46:25.820Z
Speaking of synchronization, I just do not like the assumption in _theory_. However, in _industry_, synchronization or partial synchronization is applied frequently. For example, Google's Spanner is a **globally-distributed** synchronously-replicated database. It makes me less decisive. What is your opinion?
hengxin
CC BY-SA 3.0
2012-12-07T03:40:45.633Z
I guess it is better to see how synchronization is implemented there. But it s a very interesting reference. - what I mean, it is not a natural feature of the system. It must be added to it.
AJed
CC BY-SA 3.0
2012-12-05T13:14:12.717Z
2012-12-06T21:33:56.540Z
2012-12-06T21:33:56.540Z
AJed
<p>One reason consensus problems are important is that they are <em>very simple</em> and they are kind of <em>universal problems</em> for distributed computing systems. </p>

<p>If we can solve consensus in an async distributed system we can use it to linearize actions on shared objects and obtain linearizability for shared objects. </p>

<p>For simplicity, how many problems can you think of which are simpler than agreeing on a value?</p>

<p>The impossibility result about consensus in (pure) async distributed systems tells us that we cannot solve problems we want to solve in (pure) async distributed systems without some additional "stuff". This leads to async models where we can solve consensus, e.g. randomized algorithms, fault detectors, partial synchrony models, etc. </p>

<p>This is also the reason why in practice algorithms that solve consensus like Lamport's Paxos, Google's Chubby, Apache ZooKeeper, and more recently Raft are at the core of distributed systems where we often want to replicate a state among servers.</p>

CC BY-SA 3.0
2016-02-21T19:18:13.943Z
2016-02-21T19:18:13.943Z
Kaveh
<p>I would only add that the nature of the computation is becoming increasingly distributed across the stack: many CPUs, many processes on a machine, many machines connected by LANs, many LANs connected by internets. </p>

<p>This makes the problem of common (distributed / global) state paramount - each algorithm assumes certain state and if the computation is to be performed in more than one place, then the state has to be distributed too. </p>

<p>Influential papers (<strong>Paxos</strong>, and more recently <strong>Raft</strong>) in this domain were published after the paper you are citing. Both address the issues of consensus in the presence of some failures. </p>

<p>Byzantine errors can be avoided in distributed systems using few approaches.</p>

<p>Have a look at <a href="https://en.wikipedia.org/wiki/Byzantine_fault_tolerance" rel="nofollow">Wikipedia entry on Byzantine Fault Tolerance</a>.</p>

CC BY-SA 3.0
2016-02-22T21:58:34.960Z
The FLP impossiblity result applies even in the setting of the most basic failure (crash) so I am not sure what is the point of the paragraph about avoiding Byzantine failures. Note that if we don't have failures then consensus is rather easy: one fixed process broadcasts its value and each process decides that value as soon as it is received.
Kaveh
CC BY-SA 3.0
2016-02-22T14:17:14.223Z
2016-02-22T17:17:50.300Z
2016-02-22T17:17:50.300Z
diginoise
<p>The paper you mention is important for 2 reasons:</p>

<ol>
<li>It shows that there is no <strong>asynchronous</strong> deterministic consensus algorithm that tolerates even a single crash fault. Note that in the <strong>synchronous</strong> setting,there is a deterministic algorithm that terminates in $f+1$ rounds when $\le f$ processes crash.</li>
<li>It introduces <em>bivalence</em> and <em>univalence</em> of configurations (*), which are used in many lower bounds and impossibility proofs later on. </li>
</ol>

<p><strong>Applications</strong></p>

<p>One important application of the consensus problem is the election of a coordinator or leader in a fault-tolerant environment for initiating some global action. A consensus algorithm allows you to do this on-the-fly, without fixing a "supernode" in advance (which would introduce a single point of failure). </p>

<p>Another application is maintaining consistency in a distributed network: Suppose that you have different sensor nodes monitoring the same environment. In the case where some of these sensor nodes crash (or even start sending corrupted data due to a hardware fault), a consensus protocol ensures robustness against such faults.</p>

<hr>

<p>(*) A run of a distributed algorithm is a sequence of configurations. A configuration is a vector of the local states of the processes. Each process executes a deterministic state machine. Any correct consensus algorithm must eventually reach a configuration where every process has decided (irrevocably) on the same input value. A configuration $C$ is $1$-<em>valent</em> if, no matter what the adversary does, all possible extensions of $C$ lead to a decision value of $1$. Analogously, we can define $0$-<em>valency</em>. A configuration $C$ is <em>bivalent</em> if both decisions are reachable from $C$ (which one of the two is reached depends on the adversary). Clearly, no process can have decided in a bivalent configuration $C$, as otherwise we get a contradiction to agreement! So if we can construct an infinite sequence of such bivalent configurations, we have shown that there is no consensus algorithm in this setting.</p>

CC BY-SA 3.0
2012-12-12T09:40:44.230Z
@AJed As a supplement: I have glanced over the paper [synchronization](http://dl.acm.org/citation.cfm?id=102808) by Maurice Herlihy and now can present one additional great theoretical implications of consensus problem. Using the idea of **consensus number**, one can show that there is an infinite hierarchy of synchronization primitives, such that no primitive at one level can be used for a wait-free implementation of any primitives at higher levels. Put simply, consensus problem severs as a unified theory on defining the relative _power_ of primitive synchronization operations. It is elegant.
hengxin
CC BY-SA 3.0
2013-02-28T09:26:15.033Z
I have some difficulty in understanding the proof of the FLP impossibility result. Could you give me some hints? Please refer to [FLP proof] (http://stackoverflow.com/q/15131730/1833118). Thanks.
hengxin
CC BY-SA 3.0
2012-12-06T04:52:48.267Z
2012-12-12T03:38:35.397Z
2012-12-12T03:38:35.397Z
Peter
<p>In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One Faulty Process" received the <a href="http://www.podc.org/influential/2001-influential-paper/">2001 PODC Influential Paper Award</a>.</p>

<p>So why is the consensus problem so important? What can we achieve with consensus both in theory and in practice? </p>

<p>Any references or expositions would be really helpful.</p>

<reference-request><big-picture><dc.distributed-comp>
Why is the consensus problem so important in distributed computing?
hengxin
# Why is the consensus problem so important in distributed computing?

(Asked by: username_0 on 2012-12-05)

In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One Faulty Process" received the [2001 PODC Influential Paper Award](http://www.podc.org/influential/2001-influential-paper/).

So why is the consensus problem so important? What can we achieve with consensus both in theory and in practice?

Any references or expositions would be really helpful.

**Tags:** reference-request, big-picture, dc.distributed-comp


---

## 4 answers

### Answer by username_4 on 2012-12-06. Score: 18 | Accepted answer

The paper you mention is important for 2 reasons:

1. It shows that there is no **asynchronous** deterministic consensus algorithm that tolerates even a single crash fault. Note that in the **synchronous** setting,there is a deterministic algorithm that terminates in $f+1$ rounds when $\le f$ processes crash.
2. It introduces *bivalence* and *univalence* of configurations (\*), which are used in many lower bounds and impossibility proofs later on.

**Applications**

One important application of the consensus problem is the election of a coordinator or leader in a fault-tolerant environment for initiating some global action. A consensus algorithm allows you to do this on-the-fly, without fixing a "supernode" in advance (which would introduce a single point of failure).

Another application is maintaining consistency in a distributed network: Suppose that you have different sensor nodes monitoring the same environment. In the case where some of these sensor nodes crash (or even start sending corrupted data due to a hardware fault), a consensus protocol ensures robustness against such faults.

---

(\*) A run of a distributed algorithm is a sequence of configurations. A configuration is a vector of the local states of the processes. Each process executes a deterministic state machine. Any correct consensus algorithm must eventually reach a configuration where every process has decided (irrevocably) on the same input value. A configuration $C$ is $1$-*valent* if, no matter what the adversary does, all possible extensions of $C$ lead to a decision value of $1$. Analogously, we can define $0$-*valency*. A configuration $C$ is *bivalent* if both decisions are reachable from $C$ (which one of the two is reached depends on the adversary). Clearly, no process can have decided in a bivalent configuration $C$, as otherwise we get a contradiction to agreement! So if we can construct an infinite sequence of such bivalent configurations, we have shown that there is no consensus algorithm in this setting.

> **Comments:**
> **username_0**: @username_1 As a supplement: I have glanced over the paper [synchronization](http://dl.acm.org/citation.cfm?id=102808) by Maurice Herlihy and now can present one additional great theoretical implications of consensus problem. Using the idea of **consensus number**, one can show that there is an infinite hierarchy of synchronization primitives, such that no primitive at one level can be used for a wait-free implementation of any primitives at higher levels. Put simply, consensus problem severs as a unified theory on defining the relative _power_ of primitive synchronization operations. It is elegant.  
> **username_0**: I have some difficulty in understanding the proof of the FLP impossibility result. Could you give me some hints? Please refer to [FLP proof] (http://stackoverflow.com/q/15131730/1833118). Thanks.  

---

### Answer by username_1 on 2012-12-05. Score: 8

It shows that there are no fault-tolerant deterministic algorithm. Quite a strong theoretical result, which forces designers to deal differently with fault-tolerance, some of which are synchronization and randomization.

Comment: In my opinion, synchronization is an additional assumption of the system that are hardly found in practical applications.

For references, check [the Wikipedia link](http://en.wikipedia.org/wiki/Consensus_%28computer_science%29#Applications_of_consensus_protocols).
Check also this [blog](http://jsaia.wordpress.com/2009/08/21/consensus/) for practical applications

> **Comments:**
> **username_0**: Yes, I prefer randomization to synchronization. The environment in which distributed computing plays is very poor in the sense of asynchronization, unbounded delay, unexpected failure, and too much non-deterministic. As long as it is not perfect, why don't we use randomization, achieving some guarantees while avoiding too much complexity.  
> **username_0**: Speaking of synchronization, I just do not like the assumption in _theory_. However, in _industry_, synchronization or partial synchronization is applied frequently. For example, Google's Spanner is a **globally-distributed** synchronously-replicated database. It makes me less decisive. What is your opinion?  
> **username_1**: I guess it is better to see how synchronization is implemented there. But it s a very interesting reference. - what I mean, it is not a natural feature of the system. It must be added to it.  

---

### Answer by username_2 on 2016-02-21. Score: 6

One reason consensus problems are important is that they are *very simple* and they are kind of *universal problems* for distributed computing systems.

If we can solve consensus in an async distributed system we can use it to linearize actions on shared objects and obtain linearizability for shared objects.

For simplicity, how many problems can you think of which are simpler than agreeing on a value?

The impossibility result about consensus in (pure) async distributed systems tells us that we cannot solve problems we want to solve in (pure) async distributed systems without some additional "stuff". This leads to async models where we can solve consensus, e.g. randomized algorithms, fault detectors, partial synchrony models, etc.

This is also the reason why in practice algorithms that solve consensus like Lamport's Paxos, Google's Chubby, Apache ZooKeeper, and more recently Raft are at the core of distributed systems where we often want to replicate a state among servers.


---

### Answer by username_3 on 2016-02-22. Score: 0

I would only add that the nature of the computation is becoming increasingly distributed across the stack: many CPUs, many processes on a machine, many machines connected by LANs, many LANs connected by internets.

This makes the problem of common (distributed / global) state paramount - each algorithm assumes certain state and if the computation is to be performed in more than one place, then the state has to be distributed too.

Influential papers (**Paxos**, and more recently **Raft**) in this domain were published after the paper you are citing. Both address the issues of consensus in the presence of some failures.

Byzantine errors can be avoided in distributed systems using few approaches.

Have a look at [Wikipedia entry on Byzantine Fault Tolerance](https://en.wikipedia.org/wiki/Byzantine_fault_tolerance).

> **Comments:**
> **username_2**: The FLP impossiblity result applies even in the setting of the most basic failure (crash) so I am not sure what is the point of the paragraph about avoiding Byzantine failures. Note that if we don't have failures then consensus is rather easy: one fixed process broadcasts its value and each process decides that value as soon as it is received.  

---

