My thoughts as I read the paper

In this seminal work, Leslie Lamport describes the Paxos algorithm, which borrows its name and behavior from the way the ancient parliament of the Aegean island of Paxos conducted its affairs in regard to passing laws.

The algorithm helps maintain a distributed log consisting of various entries across multiple nodes in a cluster. In practice, this is used to solve consistency issues in distributed databases.

What I find most fun about this paper so far is that it’s not written to be a “technical” paper, but instead reads like a historical account. While reading this paper I imagined the voice of Dr. Carl Sagan narrating how the ancient Paxon Parliament functioned on an episode of Cosmos. I grew intrigued and looked up whether this account of the Paxon parliament was true, only to learn that this is a literary device used by the author to make a dense topic more accessible. I wish all technical papers were written this way. On page 6 of the paper I lost my enthusiasm for the allegory. As I dived into the mathematical proofs, the allegory of the parliament was so obtuse that I laughed, wondering whether the author was being funny. I then fast-forwarded to read Section 4 of the paper, which concerns computer scientists and does away with the parliament parlance.

This paper is really old. The idea was conceived sometime in the late 80s, and the paper was submitted in 1990 but wasn’t published until May 1998.

The fact that it was published so late, and even then it needed Lamport to come up with a simplified version, is perhaps a lesson that despite our innate need for teaching with storytelling, it’s perhaps not a great fit when it comes to complex ideas, certainly not as complex as distributed systems.

It’s interesting how we humans love stories — they help us make sense of the world. But sometimes, when ideas get really complex, like the ones behind distributed systems, stories can actually get in the way. Leslie Lamport’s original paper took years to be accepted, partly because he wrapped his ideas in a kind of story that was hard to follow. Eventually, he had to come back and explain things more simply, without the storytelling. It’s a reminder that while stories are powerful, sometimes clarity and straightforwardness are what we need most to understand the deeper truths of how things really work.

  1. The Part-time Parliament – the original paper faced a lot of delays in getting published owing to its unique storytelling technique, which made it appear very convoluted to a lot of readers.

  2. Paxos Made Simple – the author heard a lot of complaints from readers that the original 1998 paper was too hard to read and understand. He then compiled this simplified version in 2001. The abstract is literally a single line: “The Paxos algorithm, when presented in plain English, is very simple.”

1.2 Requirements

  • Legislators may join and leave the Chamber, never remaining for the entire session.
  • Legislators maintain a ledger which contains the numbers of decrees that have been passed.
  • Ledger entries are immutable.
  • Ledgers must be consistent, i.e. no two legislators should have a decree with the same number containing contradictory entries.
  • Ledgers may contain decrees with missing entries, if they haven’t yet learnt that a specific entry has been created for that decree.
  • Fulfilling consistency by having a ledger full of decrees with missing entries is not desired. Some criterion is required to ensure all decrees are eventually passed and recorded in the ledgers.
  • Progress Condition: If a majority of legislators were present in the Chamber, and no one had left or joined for a sufficient period of time, any decree proposed by a legislator would be passed and every passed decree would be recorded within the ledger of every legislator in the Chamber.

1.3 Assumptions

  • Legislators might lose track of things if they left the Chamber.
  • Legislators maintain notes, which are mutable compared to the ledger, which is immutable.
  • Legislators use hourglass timers to keep track of time.
  • The ledger is always accessible to the legislator, while notes may or may not be lost when the legislator left the Chamber.
  • Messengers are used to pass messages between legislators in the parliament.
  • Message delay, message duplication, and message loss are accepted parts of the system.

Notes

  1. The safety of the algorithm lies in the prepare(n, v) phase where the acceptors respond with a list of accepted values for any proposals with n > n_p. This response of accepted values permits the proposer to change its tune, and use the v from the accepted value (from the highest n).

The final protocol permits multiple proposals while preserving the previously chosen value in later successful proposals.

A common process in both majorities ensures consistency

  1. Livelocks: The algorithm would be susceptible to livelocks where two proposers would infinitely issue proposals with increasing numbers without any of those proposals being chosen. This is avoided by electing a Distinguished Proposer who is in charge of making proposals.
  2. The process of electing a Distinguished Leader is itself a problem of distributed consensus. The paper does not speak about a specific implementation of a leader election algorithm.
  3. Paxos ensures safety, i.e. correctness in the face of failures – data will never be inconsistent across nodes.
  4. Paxos conditionally ensures liveness, i.e. additional data continues to be written, provided a majority of nodes are working.
  5. Paxos works even if the system elects multiple leaders. This may result in slowing the propagation of proposals but does not violate safety.
  6. Paxos meets the Consistency & Partitioning criteria of the CAP theorem.

Open question

  1. The paper describes a basic Paxos. There are other variants used in practical systems like Multi-Paxos. What kind of problems does Multi-Paxos address?