Introduction to Paxos

Motivation: Log replication via consensus

Paxos is a consensus algorithm used by multiple entities to agree on something of interest, such as maintaining consistency among multiple copies of data. As we learned in our state machine replication chapter, we can model a broad range of computation as a state machine, and replicating such a state machine at different nodes provides us fault tolerance. Commands transition a state machine from one consistent state to the next. To ensure consistency, it is necessary to establish consensus among the replicas of the state machine regarding the specific command to be executed and the order in which it should be executed. Paxos being a consensus algorithm is a natural choice in this scenario. (We will learn about Paxos in the context of state machine replication because it is generic and applicable for many use cases.)

We will use the Paxos algorithm to achieve consensus on a single valueThis value can be arbitrarily complex in nature. across state machine replicas. In the real world, Paxos-based solutions are used to implement replicated logs. A log can be viewed as a series of placeholders (called a slot) to save clients' commands. These logs record the commands of clients, one per slot. Paxos is agnostic about the specifics of these commands because they are application specific. These commands could be machine instructions (for example, jmp 0x12366) or keys and their associated values in a hash table or any other state machine. These logs can be viewed as sequential read-ahead files. Once consensus has been achieved on the slot's commands, these commands are executed on the local state machine. Each execution transitions a state machine from one consistent state to the next.

We use a Paxos instance to achieve consensus on a single slot of the log, as shown in the following slide deck. There can be multiple clients wanting to write their command at a specific slot of the log, and the Paxos algorithm helps them reach a consensus on whose value will be chosenWe say a value is chosen when a majority of replica servers have agreed on a value. in the slot. Multiple instances of Paxos can be active concurrently for different slot numbers.