Paxos
Paxos Protocol
Computer Algorithm: To achieve agreement, one or more of the computers proposes a value to Paxos (Proposer). Consensus is achieved when a majority of the computers running Paxos agrees on one of the proposed values (Acceptor).
Paxos defines several different roles (from Sylladb):
- Proposers, who receive requests (values) from clients and try to convince acceptors to accept the value they propose.
- Acceptors, who accept certain proposed values from proposers and let proposers know whether a different value was accepted. A response from an acceptor represents a vote for a particular proposal.
- Single acceptor. Multiple proposers will concurrently propose various values to a single acceptor. The acceptor chooses one of these proposed values (Understanding Paxos)
- Learners, who announce the outcome to all participating nodes.
- For asynchronous systems.
- Leader-based protocol where each process has an estimate of who the current leader is.
- When a process desires to achieve consensus on a value, it sends it to the current leader.
- The leader launches a consensus algorithm to ensure agreement.
consensus algorithm
From (understanding paxos)/6603 Lectures/martinfowler
Phase 0
Client asks a leader/proposer for a value.
Phase 1 (Prepare)
A proposer asks all the working acceptors whether anyone already received a proposal. If the answer is no, propose a value.
- Choose new ballot number (establish latest genaration clock)
- Send new ballot to sites and wait for ack (along with result of previous votes)
Phase 2 (Accept)
- After receiving ack, propose value with ballot
- If a majority of acceptors agree to this value then that is our consensus.
Resources
Paxos - Wikipedia
Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors.
- Paxos is usually used where durability is required
The Part-Time Parliament - Leslie Lamport
What is Paxos Consensus Algorithm? Definition & FAQs | ScyllaDB
Understanding Paxos
Paxos - martin fowler
Three phases.
- Prepare phase: establish the latest Generation Clock and gather any already accepted values.
- Leader chooses a new unique ballot number, which is sent to all sites,
- Waits to learn the outcome of all smaller ballots from a majority of sites.
- Accept phase: propose a value for this generation for replicas to accept.
- Commit Phase: let all the replicas know that a value has been chosen.
What is Paxos Consensus Algorithm? Definition & FAQs | ScyllaDB