Consensus problem of distributed systems

Question

I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On the other hand, there are multiple consensus protocols used in practical systems to synchronize distributed state machines like Paxos and Raft. It seems like the key to this perceived contradiction is what is called failure detection.

My question is the following: What does protocols like Paxos and Raft give up, i.e. how are they not contradicting the theorem? How does failure detection fit in here?

Are there any papers that discuss these relationships that are worth looking at?

Answer 1

The FLP theorem [1] says that

It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage

1. changing the system assumptions

   • Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
   • Assuming a partial synchronous system in which failure detectors [3] are used

2. or changing the problem statement

   • No guarantee for termination (progress) such as Paxos [4]
   • Randomized protocol [5]
   • No need to agree on a single value such as in $k$-set agreement problem
   • No need to agree on exact values in approximate agreement

---

[1] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

[4] Paxos Made Simple TR. By Lamport

[5] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.