Consensus

Paxos is a family of best-effort protocols proposed by L. Lamport for reaching consensus within an asynchronous communications network with unreliable participants. Advanced versions of Paxos can cope with byzantine behaviours.

More details :

Lamport, L. (2001). Paxos made simple. ACM Sigact News, 32(4), 18-25.

Basic Paxos

Basic Paxos is composed of three roles:

clients : processors that sends request.
Acceptors : processors that accept values, where a value is chosen if a majority accept.
Proposers : processors that receive the user's request, and who will try to get the consensus of the acceptors.
Learner : processors that will save the action log, execute it and transmit the response of the request to the user.

$Note$ : An agent can do several roles at the same time.

The paxos process is executed in two phases.

The preparation phase.
- The Proposer initializes or increments his id.
- The Proposer sends each Acceptor a Propose(topic, id). id is the largest id seen by the Proposer and topic is the topic of the concensus.
- Acceptors return Promise(topic, id, val_accepted) if the largest id sent is met, otherwise they reject with a Nak(id). val_accepted is the value accepted during a consensus (default is null).
- If the majority has made a promise, we pass to second phase, otherwise we go back to the first step.
The acceptance phase.
- The Proposer sends an Accept(topic, id, value) to the Acceptors. value is chosen by Client if all val_accepted are null, otherwise it will be the value val_accepted.
- Acceptors return Accepted(topic, id, value) if the id sent is the largest, Nak(topic, id) otherwise.
- If the acceptance is not successful, we go back to the first phase, otherwise we send the Learner the associated request.

Here is a simple sequence of events.

Here is a more complex sequence of events.

sequenceDiagram Client->>Proposer1: request(topic, val1) Client->>Proposer2: request(topic, val2) Proposer1->>Acceptor1:Propose(topic, 1) note over Acceptor1: The first Proposer is always accepted. Acceptor1->>Proposer1:Promise(topic, 1, null) Proposer2->>Acceptor1:Propose(topic, 1) Proposer2->>Acceptor2:Propose(topic, 1) note over Acceptor2: The first Proposer is always accepted. Acceptor2->>Proposer2:Promise(topic, 1, null) Acceptor1->>Proposer2:Nak(topic, 1) Proposer2->>Acceptor1:Propose(topic, 2) Proposer1->>Acceptor2:Propose(topic, 1) Acceptor2->>Proposer1:Nak(topic, 1) Proposer2->>Acceptor2:Propose(topic, 2) Acceptor2->>Proposer2:Promise(topic, 2, null) Proposer2->>Acceptor1:Accept(topic, 2, val2) Proposer2->>Acceptor2:Accept(topic, 2, val2) Acceptor2->>Proposer2:Accepted(topic, 2, val2) Acceptor1->>Proposer2:Accepted(topic, 2, val2) Proposer2->>Leaner:Decide(topic, val2) Leaner->>Client:res2 note over Client: res2 is the answer of the request(topic, val2). note over Proposer1: Continue for the consensus of the request(topic, val1). Proposer1->>Acceptor1:Propose(topic, 3) Proposer1->>Acceptor2:Propose(topic, 3) Acceptor2->>Proposer1:Promise(topic, 3, val2) Acceptor1->>Proposer1:Promise(topic, 3, val2) Proposer1->>Acceptor1:Accept(topic, 3, val2) Proposer1->>Acceptor2:Accept(topic, 3, val2) Acceptor2->>Proposer1:Accepted(topic, 3, val2) Acceptor1->>Proposer1:Accepted(topic, 3, val2) Proposer1->>Leaner:Decide(topic, val2) Leaner->>Client:res2 note over Client: res2 is the answer of the request(topic, val2).

Multi-Paxos

MultiPaxos has the same roles as BasicPaxos, what changes is that instead of having a consensus for a single value, it is done for a series of values.

The paxos process is executed in two phases.

The preparation phase.
- The Proposer initializes or updates his id.
- The Proposer sends each Acceptor a Propose(topic, id). id is the largest id seen by the Proposer and topic is the topic of the concensus.
- Acceptors return Promise(topic, id, list_val_accepted) if the largest id sent is met, otherwise they reject with a Nak(id). list_val_accepted is the list of value accepted during a consensus (default is null).
- If the majority has made a promise, we pass to second phase, otherwise we go back to the first step.
The acceptance phase.
- The Proposer sends an Accept(topic, id, list_value) to the Acceptors. value is chosen by Client if all val_accepted are null, otherwise it will be the list of value list_val_accepted where the new value is added.
- Acceptors return Accepted(topic, id, list_value) if the id sent is the largest, Nak(topic, id) otherwise.
- If the acceptance is not successful, we go back to the first phase, otherwise we send the Learner the associated request.

Let's take the previous examples:

sequenceDiagram Client->>Proposer: request(topic, val) Proposer->>Acceptor1:Propose(topic, 1) note over Acceptor1: The first Proposer is always accepted. Proposer->>Acceptor2:Propose(topic, 1) note over Acceptor2: The first Proposer is always accepted. Acceptor2->>Proposer:Promise(topic, 1, null) Acceptor1->>Proposer:Promise(topic, 1, null) Proposer->>Acceptor1:Accept(topic, 1, {val}) Proposer->>Acceptor2:Accept(topic, 1, {val}) Acceptor2->>Proposer:Accepted(topic, 1, {val}) Acceptor1->>Proposer:Accepted(topic, 1, {val}) Proposer->>Leaner:Decide(topic, {val}) Leaner->>Client:res note over Client: res is the answer of the request(topic, val). Client->>Proposer: request(topic, val2) Proposer->>Acceptor1:Propose(topic, 2) note over Acceptor1: The first Proposer is always accepted. Proposer->>Acceptor2:Propose(topic, 2) note over Acceptor2: The first Proposer is always accepted. Acceptor2->>Proposer:Promise(topic, 2, {val}) Acceptor1->>Proposer:Promise(topic, 2, {val}) Proposer->>Acceptor1:Accept(topic, 2, {val, val2}) Proposer->>Acceptor2:Accept(topic, 2, {val, val2}) Acceptor2->>Proposer:Accepted(topic, 2, {val, val2}) Acceptor1->>Proposer:Accepted(topic, 2, {val, val2}) Proposer->>Leaner:Decide(topic, {val, val2}) Leaner->>Client:res2 note over Client: res2 is the answer of the request(topic, val2).

sequenceDiagram Client->>Proposer1: request(topic, val1) Client->>Proposer2: request(topic, val2) Proposer1->>Acceptor1:Propose(topic, 1) note over Acceptor1: The first Proposer is always accepted. Acceptor1->>Proposer1:Promise(topic, 1, null) Proposer2->>Acceptor1:Propose(topic, 1) Proposer2->>Acceptor2:Propose(topic, 1) note over Acceptor2: The first Proposer is always accepted. Acceptor2->>Proposer2:Promise(topic, 1, null) Acceptor1->>Proposer2:Nak(topic, 1) Proposer2->>Acceptor1:Propose(topic, 2) Proposer1->>Acceptor2:Propose(topic, 1) Acceptor2->>Proposer1:Nak(topic, 1) Proposer2->>Acceptor2:Propose(topic, 2) Acceptor2->>Proposer2:Promise(topic, 2, null) Proposer2->>Acceptor1:Accept(topic, 2, {val2}) Proposer2->>Acceptor2:Accept(topic, 2, {val2}) Acceptor2->>Proposer2:Accepted(topic, 2, {val2}) Acceptor1->>Proposer2:Accepted(topic, 2, {val2}) Proposer2->>Leaner:Decide(topic, {val2}) Leaner->>Client:res2 note over Client: res2 is the answer of the request(topic, val2). note over Proposer1: Continue for the consensus of the request(topic, val1). Proposer1->>Acceptor1:Propose(topic, 3) Proposer1->>Acceptor2:Propose(topic, 3) Acceptor2->>Proposer1:Promise(topic, 3, {val2}) Acceptor1->>Proposer1:Promise(topic, 3, {val2}) Proposer1->>Acceptor1:Accept(topic, 3, {val2, val1}) Proposer1->>Acceptor2:Accept(topic, 3, {val2, val1}) Acceptor2->>Proposer1:Accepted(topic, 3, {val2, val1}) Acceptor1->>Proposer1:Accepted(topic, 3, {val2, val1}) Proposer1->>Leaner:Decide(topic, {val2, val1}) Leaner->>Client:res1 note over Client: res1 is the answer of the request(topic, val1).