Paxos is

A protocol for solving consensus in a network which is supposed to be unreliable and fallible.

Participants & Roles

Participants in Paxos taka one of three roles:

• Proposers
• Acceptors
• Learners

And single process can be a proposer, an acceptor and a learner at the same time.

Phases

It has two phases:

• Voting(or propose)
• Replication

Algorithm

Every proposal has value, requested by the client and unique monotonically increasing proposal number.

As you can imagine, the proposer is an initial point of contact for the client. They attempt to collect votes from the quorum of acceptors.
When voting finishes, acceptors distribute the information to learners and learners increase replication factor of the value that's agreed.

Voting phase

• Proposer sends Prepare(n) message.
  • n is a proposal number
• Acceptor receives the prepare request with the following invariants
  • If the acceptor hasn't responded to a prepare request with a higher sequence number, it will NOT accept any proposal with a lower sequence number.
  • If this acceptor has already accepted any other proposal earlier, it responds with a Promise(m, v) message, notifying the proposer that it has already accepted the proposal with a sequence number m.
  • If this acceptor has already responded to a prepare request with a higher sequence number, it notifies the proposer about the existence of a higher number
  • Acceptor can respond to more than one prepare request, as long as the later one has a higher sequence number.

Replication Phase

Proposer who became a leader for that consensus starts replication.

It commits the proposal by sending acceptors an Accept!(n,v) message with value v and proposal number n.

If that's accepted by Acceptor, and the proposer collects enough votes, consensus is reached.

As noted above, Acceptor will accept proposal UNLESS during the propose phase it has already responded to Prepare(m) where m is greater than n. If it has to reject the proposal, it notifies the proposer about it sending it by highest sequence number it has seen.

To summarize, the execution flow will be like this:

Code example in Rust

The following is local implementation for Paxos to put it into perspective.

use std::collections::HashMap;

#[derive(Debug, Clone)]
struct Proposal {
    proposal_number: u64, 
    value: String,        
}

#[derive(Debug)]
struct Acceptor {
    proposal_number: Option<u64>, // Highest proposal ID it has promised not to accept lower
    accepted_id: Option<u64>,     // ID of the accepted proposal
    accepted_value: Option<String>, // Value of the accepted proposal
}

impl Acceptor {
    fn new() -> Self {
        Acceptor {
            proposal_number: None,
            accepted_id: None,
            accepted_value: None,
        }
    }

    fn prepare(&mut self, proposal_number: u64) -> Result<Option<(u64, String)>, u64> {
        if let Some(promised_id) = self.proposal_number {
            // Invariant #1
            // If the `acceptor` hasn't responded to a prepare request with a higher sequence number,
            // it will NOT accept any proposal with a lower sequence number

            // Invariant #3
            // If this `acceptor` **has already responded** to a prepare request with a higher sequence number,
            // it notifies the `proposer` about the existence of a higher number

            if proposal_number <= promised_id {
                return Err(promised_id);
            }
        }
        self.proposal_number = Some(proposal_number);

        // Invariant #2
        // If this `acceptor` **has already accepted** any other proposal earlier, it responds with a `Promise(m, v)` message,
        // notifying the proposer that it has already accepted the proposal with a sequence number m.
        if let (Some(accepted_id), Some(accepted_value)) = (self.accepted_id, &self.accepted_value)
        {
            Ok(Some((accepted_id, accepted_value.clone())))
        } else {
            Ok(None)
        }
    }

    fn accept(&mut self, proposal_id: u64, value: String) -> Result<(), String> {
        if let Some(promised_id) = self.proposal_number {
            if proposal_id < promised_id {
                return Err(format!(
                    "Proposal ID {} is less than promised ID {}",
                    proposal_id, promised_id
                ));
            }
        }
        self.accepted_id = Some(proposal_id);
        self.accepted_value = Some(value);
        Ok(())
    }
}

struct Proposer {
    id: u64,
    quorum_size: usize,
}

impl Proposer {
    fn propose(&self, value: String, acceptors: &mut HashMap<u64, Acceptor>) -> Option<String> {
        let proposal_id = self.id;

        // Phase 1: Prepare
        let mut promises = Vec::new();
        for acceptor in acceptors.values_mut() {
            if let Ok(result) = acceptor.prepare(proposal_id) {
                promises.push(result);
            }
        }

        // Check if we have a quorum
        if promises.len() < self.quorum_size {
            println!("Failed to gather a quorum during Prepare phase.");
            return None;
        }

        // Use the highest proposal's value if available
        let mut final_value = value;
        if let Some((_, highest_value)) = promises
            .into_iter()
            .filter_map(|opt| opt)
            .max_by_key(|(id, _)| *id)
        {
            final_value = highest_value;
        }

        // Phase 2: Accept
        let mut accepts = 0;
        for acceptor in acceptors.values_mut() {
            if acceptor.accept(proposal_id, final_value.clone()).is_ok() {
                accepts += 1;
            }
        }

        // Check if we have a quorum
        if accepts >= self.quorum_size {
            println!(
                "Proposal {} with value '{}' was accepted!",
                proposal_id, final_value
            );
            return Some(final_value);
        } else {
            println!("Failed to gather a quorum during Accept phase.");
            return None;
        }
    }
}

fn main() {
    // Create 5 acceptors
    let mut acceptors: HashMap<u64, Acceptor> = (0..5).map(|id| (id, Acceptor::new())).collect();

    // Create a proposer
    let proposer = Proposer {
        id: 1,
        quorum_size: 3, // Quorum size is majority (e.g., 3 out of 5)
    };

    // Propose a value
    let value = "ConsensusValue".to_string();
    if let Some(agreed_value) = proposer.propose(value.clone(), &mut acceptors) {
        println!("Consensus reached on value: {}", agreed_value);
    } else {
        println!("Consensus could not be reached.");
    }
}

Problem of classic Paxos

For every round, vote is made and this is impractical for real-world systems due to performance concerns. To overcome this, Multi-paxos was suggested.