19
$\begingroup$

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.

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.

|cite|improve this question|||||
$\endgroup$
18
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ @AJed As a supplement: I have glanced over the paper synchronization 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. $\endgroup$ – hengxin Dec 12 '12 at 9:40
  • 1
    $\begingroup$ I have some difficulty in understanding the proof of the FLP impossibility result. Could you give me some hints? Please refer to [FLP proof] (stackoverflow.com/q/15131730/1833118). Thanks. $\endgroup$ – hengxin Feb 28 '13 at 9:26
  • $\begingroup$ "where every process has decided" maybe should be "where every correct process has decided"? $\endgroup$ – nbro Nov 9 '18 at 17:59
  • $\begingroup$ You should explain who the adversary is in "no matter what the adversary does". $\endgroup$ – nbro Nov 9 '18 at 18:00
  • $\begingroup$ "all possible extensions of C", what do you mean by "extension of C"? What is an extension of a configuration, in general? $\endgroup$ – nbro Nov 9 '18 at 18:03
7
$\begingroup$

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. Check also this blog for practical applications

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hengxin Dec 7 '12 at 1:30
  • 1
    $\begingroup$ 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? $\endgroup$ – hengxin Dec 7 '12 at 1:46
  • $\begingroup$ 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. $\endgroup$ – AJed Dec 7 '12 at 3:40
  • $\begingroup$ In general, you should not give as reference Wikipedia. I have just read that Wikipedia article: it's quite incomplete and unorganised; it could also be confusing. $\endgroup$ – nbro Nov 9 '18 at 17:55
5
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Feb 22 '16 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.