Discussion for: Leslie Lamport, "Paxos Made Simple" (2001)

Paper overview

The paper was written as a response to Lamport's original paper on the Paxos algorithm, "The Part-Time Parliament.". "Paxos Made Simple" and "The Part-Time Parliament" both present the same algorithm to achieve consensus (given algorithm termination) among distributed servers in the asynchronous network model. The algorithm itself assumes the crash fault model and guarantees safety, but not liveness. Each participating server can be a combination of the following roles: proposer, acceptor, and learner. Proposers propose values to a majority of acceptors and the acceptors accept proposed values. Learners only ever learn about values that were accepted. The paper concludes with a description of a state machine implementation of Paxos.

Discussion questions

Q1

Take a few minutes (no more than two or three) to skim through the original Paxos paper that predated "Paxos Made Simple". Why do you think this paper was considered so hard to understand that it warranted a simpler rewrite?

Discussion summary for Q1

The original paper that Lamport wrote was written as a narrative taking place on Paxos, one of the Greek Ionian Islands. To understand the original paper, readers are expected to extrapolate the mappings of roles in Greek parliament to roles in a distributed system, as well as translate the presented procedures in terms of Greek parliament to procedures to be performed in a distributed system. The original paper also was also extremely technical, with many of the required conditions in Paxos expressed in first-order logic, which is assumedly one of the things Lamport was referring to when he noted in "Paxos Made Simple" that "[the] Paxos algorithm, when presented in plain English, is very simple." So why did Lamport write the paper this way? Most likely because Lamport had already established himself in the field and no longer felt the need to prove anything. He wrote it as a fantastical narrative solely because he wanted to and probably found it more interesting.

Q2

(Contributed by @aakash-mishra)

By having acceptors respond with a promise that contains “extra information” about the proposal they have already accepted, other proposers are limited in what values they can propose in their accept messages. This seems like it ought to be enough to guarantee termination. Why, then, does the paper say that a distinguished proposer (leader) should be elected to guarantee termination?

Discussion summary for Q2

The paper states in section 2.4 that "[it's] easy to construct a scenario in which two proposers each keep issuing a sequence of proposals with increasing numbers, none of which are ever chosen." This specific scenario is referred to as the "Dueling Proposers." Lamport suggests that a distinguished proposer be elected in order to guarantee forward progress. Since there is only ever one proposer proposing values to accept, there is never a case in which two proposers are dueling. Another proposer must be elected to replace a failed distinguished proposer. Regardless of whether or not the election succeeds, safety is still ensured by Paxos.

Q3

(Contributed by @reeselevine)

In order to guarantee correctness, Paxos requires each proposer to issue unique proposal numbers. The paper says that this can be done by having each proposer choose from a disjoint set of proposal numbers. In practice, how can we ensure that each proposer chooses a unique number?

Discussion summary for Q3

One way of having proposers choose unique proposal numbers from disjoint sets is to make use of congruence classes modulo n, where n is the number of proposers. Assume there are n proposers. Proposer 0 can only use proposal numbers from the set of integers congruent to 0 mod n: { 0, n, 2n, 3n, … }. Proposer 1 can only use proposal numbers from the set of integers congruent to 1 mod n: { 1, n + 1, 2n + 1, 3n + 1, … }. So, any proposer m, where 0 <= m < n (assuming 0-based indexing) can only select integers in a monotonically increasing fashion from the set of numbers congruent to m modulo n.

Another way of having proposers choose unique proposal numbers is simply by ID-ing them and appending a local timestamp onto their ID. A proposer ID is simply a number unique to the proposer. The result of appending a local timestamp onto an ID, then, is a unique proposal. A sequence of these proposals must be monotonically increasing in value if system timestamps are assumed never to drift backwards.

Note that both these approaches make use of common knowledge of the number of proposers in the system. This is fine since the Paxos algorithm itself already needs to establish common knowledge about the number servers acting as each of the roles in the system (proposer, acceptor, learner).

Errata

Running list of typos / issues found in the paper:

• n/a

Other

Any interesting points or questions from the group discussion that didn't fit above:

• n/a