Consensus
Consensus is the act of achieving agreement on facts among a collection of running programs.
Consensus can be achieved by have a well-known master machine that is the unique arbiter of fact. All other machines are clients that submit facts to the master and receive the consensus result from the master. The relative value of the facts is not at issue, just that there be agreement.
However, there are reasons to reject such a centralized mechanism for consensus. Paxos is one of the oldest and most known algorithm for achieving consensus in a distributed manner. A pool of machines, called the Acceptors, are proposed facts by the Proposers. The Proposers go through two rounds of messaging with the Acceptors, exiting each round once it has received responses from a majority (in general, a quorum) of Acceptors. In this version, the Proposers are also Learners, they learn when a consensus is reached and they learn the consensus value.
The consensus problem is impossible to solve in full generality, so consensus algorithms look for ways to introduce a little slack. For Paxos, it is always correct when it does come to consensus, but Proposers might need to take a few attempts at consensus.
NAME
mu-paxos
SYNOPSIS
mu-paxos -p port-number -t time-out
mu-paxos -p port-number -t time-out -r rounds -s acceptor acceptor ... acceptor value
DESCRIPTION
The first form starts an Acceptor. The Acceptor loops forever or until
the optional timeout. There are no arguments in the Acceptor form of the command.
The second form starts a Proposer/Learner. All Proposers will propose the
values provided on the command line to all those acceptors provided on the
command line, and will continue with the Paxos protocol to reach consensus.
When a Proposer learns that consensus has been reached, the Proposer prints
the consensus value and exits.
OPTIONS
-p the port the server listens (is listening) on, the default is 3333
-r the number of rounds until failure, for the proposer/learner, the default is 5.
-s snooze. default 0, add 1 second for each option; inserts random delays to exercise the protocol.
-t timeout. Default is no timeout.
-v Verbose. Helpful debugging output to stdout.
BUGS
The standard implementation will use Reject messages rather than timeouts.
The implementation uses time for the proposal number, hence proposal numbers might not be unique.
HISTORY
First introduced in Spring 2023.
LAST UPDATED
16 April 2023
Description of Paxos
The program is of client-server form, where there are multiple clients and multiple servers.
The clients suggest values to the servers, and the servers agree on those values and report the agreement back to the client. This is done in two phases: The Prepare/Promise phase and the Accept/Accepted phase. The clients are called Proposers or Listeners, depending on whether they are proposing values or learning the consensus value. The servers are called Acceptors.
The phases are not synchronous. Each Proposer transitions from a phase when it has heard responses form a majority of Acceptors. The Acceptors maintain a state that transitions phases as well, but will receive propositions are any time.
Packet Formats
Prepare: OP == 1
+----+----+----+----+----+----+
| OP | proposal number |
+----+----+----+----+----+----+
Promise: OP == 2 (if no value accepted)
+----+----+----+----+----+----+
| OP | proposal number |
+----+----+----+----+----+----+
Promise: OP == 2 (if a value accepted)
+----+----+----+----+----+----+----+----+----+----+----+- ... -+----+
| OP | proposal number | promised number | value |
+----+----+----+----+----+----+----+----+----+----+----+- ... -+----+
Accept: OP == 3
+----+----+----+----+----+----+----+- ... -+----+
| OP | proposal number | value |
+----+----+----+----+----+----+----+- ... -+----+
Accepted: OP == 4
+----+----+----+----+----+----+
| OP | proposal number |
+----+----+----+----+----+----+
Reject: OP == 5
+----+----+----+----+----+----+
| OP | proposal number |
+----+----+----+----+----+----+
- OP is a 2 byte unsigned integer.
- Proposal numbers are 4 bytes unsigned integer.
- Values are null-terminated ascii strings.
- The empty value is the empty string, regardless of proposal number.
- All values are in network byte order
The micro-Paxos Algorithm
Proposer/Learner:
Receive value from input
ROUND LOOP
0) Set proposal number n equal to the unix time
Set m:v to 0:value
1) Send Prepare packets with proposal number n
2) Wait for a majority of Promise packets
a) For each Promise packet if m'>m then m:v is set to m':v'
b) If Reject packet, abort/move to next round.
c) If a majority set value to v
d) If no majority after timeout: abort/move to next round
3) Send Accept packets with value
4) Wait for a majority of Accepted packets
a) If Reject packet, abort/move to next round.
b) If majority break loop
c) If no majority after timeout: abort/move to next round.
Print value and exit
Acceptor:
set proposal number n to 0
set accepted value to NONE
1) If received a Prepare for proposal n':
a) if n'<n: send Reject
b) else:
i) set n to n'
ii) send Promise packet with stating proposal n, and the current accepted value, if any
2) If received an Accept for proposal n' and value v:
a) if n'<n: send Reject
b) else set accepted value to n':v
c) and send Accepted packet
Author: Burton Rosenberg
Created: 11 April 2023
Last Update: 16 April 2023