Note: In future, a formal proof discussion will be added

As an ambitious guy who always takes up weirdest challenges and shoots himself on his foot, for the first minor project in our college I took up the challenge to create a distributed key value store, with a Paxos protocol for consensus. What struck me as odd was that unlike papers that discuss Raft and provide a concrete implementation details throughout, there is not such convenience on literature associated with Paxos. So of course I had to wonder how to do leader elections in the multi-paxos implementation

The paper by Leslie Lamport on his “simplified” explanation of Paxos in “Paxos Made Simple” ¹ referenced an amazing result by Lynch, Fischer and Patterson ² which finally proved a doubt which many distributed system researchers had at that time

You see, around the 1985s it was already proved that in synchronous settings, we can have a distributed consensus. Informally, synchronous models allow failures to be detected by waiting one entire step length for a reply from a processor, and presuming that it has crashed if no reply is received. But nothing had been said for the asynchronous settings (the exact details of it would be discussed soon in this article)

Before diving into the main proof, it will be a bit more pragmatic to see what the paper tries to aim at

A quick intuitive walk-through

For simplicity, assume that the configuration of a system is the combination of messages either in fly through the links, or the recent reception of a message by the processor. Bivalence refers to the fact that this configuration can go either to a $0$ decision state or a $1$ decision state. A step consists of a tranmission of messages to some processor

The main discusson of this paper is pretty much contained in the two lemmas The first lemma (Lemma 2 in paper) is

P has an initial bivalent configuration

This lemma assumes that the consensus protocol is partially correct, in that, if taken all the possible initial configurations, and taken some decisive transfers of messages between the processors, we will reach both the decisions of 1 and 0 (which is what this simplistic model in discussion limits itself to, discussed more later), which is a fair expectation, otherwise the consensus protocol won’t be needed

The benefit of this lemma is that it avoids the possibility of simple lookup of the initial state and get the decision value. This arises from the asynchronous nature of the distributed system

This combined with the second lemma (Lemma 3 in paper) leads to the actual result.

The second lemma has two parts to it. The first part discusses that for every bivalent configuration, you can always have a step such that it leads it to another bivalent configuration

The second part is very interesting, let’s say, we are at some bivalent configuration $C_1$, which after a step $e = (p,m)$ (sending message $m$ to processor $p$) and reception of the associated message by $p$ therefore, goes to $C_2$, we can find another step that takes $C_1$ to $D_1$, such that the step $e$ through the configration $D_1$ will lead to bivalent configuration

This is valid since our system is asynchronous, so we can’t rely on the fact that messages will have some ordering!

And this finally leads to the result, we cannot possibly have a protocol such that it always leads to a total consensus, even in presence of a single faulty process! If there’s ever a possible step which can take it to a univalent configuration, you can just have a bit of message re-ordering which will lead to a bivalent configuration after that step

---

1. L Lamport Paxos Made Simple 2001 ↩︎

2. Fischer, Lynch, Patterson Impossibility of Distributed Consensus with One Faulty Process 1985 ↩︎