Developed by Leslie Lamport, Paxos is a family of protocols for achieving consensus in a network of unreliable processors. Key Components:
- Proposers: Suggest values.
- Acceptors: Agree on proposed values.
- Learners: Learn the chosen value.
Operations:
- Prepare Phase: A proposer selects a proposal number and sends a prepare request to a majority of acceptors.
- Promise: Acceptors respond with a promise not to accept proposals with a number less than the received one.
- Accept Phase: The proposer sends an accept request with the proposal number and value.
- Accepted: Acceptors accept the proposal unless they’ve already promised a higher number.
Challenges:
- Complexity in implementation.
- Performance overhead due to multiple message exchanges.
Applications:
- Google’s Chubby lock service.
- Microsoft’s Autopilot cluster management.