🏝️ Paxos

Paxos is an algorithm for Consensus. The goal is to maintain a replicated, consistent append-only log; in practice, this log can record the sequence of operations, allowing all nodes to have the same processing order.

The Paxos algorithm guarantees safety—only a single proposed value can be chosen—but not liveness—some proposed value is eventually chosen, and all nodes learn of it. The method operates with a lossy, asynchronous network on nodes that can crash.

Paxos organizes nodes into three roles: proposers, acceptors, and learners. Proposers propose a new entry to append, and acceptors accept these proposals; if a proposal is accepted by a majority, it’s decided as the final value and send to the learners. We can organize this procedure into two phases: prepare and accept.

Prepare §

In the first phase, suppose node wants to propose value for entry . Then, chooses a new proposal number and sends to a majority quorum of other nodes; this message is asking the nodes if can make a proposal for with number , and if so, to suggest a value that can use.

Then, if node receives from :

1. If it already acknowledge a with , then do nothing.
2. If it previously accepted proposals for this entry, respond with where is the highest proposal number it has accepted, and is the corresponding value.
3. Otherwise, respond with

Here, means that lets make the proposal; if is given, should choose .

Accept §

In the second phase, if receives from a majority of other nodes, it sends where is the value of with highest proposal number (or original if none had values).

When receives :

1. If already acknowledged with , then do nothing.
2. Otherwise, accepts the proposal and sends to all learners.

When a learner receives from majority of acceptors, it decides . It then sends to all other learners, causing them to also decide for entry .