Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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.

share|improve this question

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
1  
@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. – hengxin Dec 12 '12 at 9:40
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. – hengxin Feb 28 at 9:26
up vote 3 down vote

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

share|improve this answer
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 Dec 7 '12 at 1:30
1  
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 Dec 7 '12 at 1:46
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 Dec 7 '12 at 3:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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