Motivation:
This paper presents the Paxos algorithm in plain English. The Paxos algorithm solves the problem of reaching consensus in a distributed system where agents may fail and messages may be dropped or delayed.
Main points:
- The Paxos algorithm has three main roles for agents: Proposers, Acceptors and Learners. These agents behave according to a set of rules prescribed by the algorithm.
- Every proposal that is sent has a proposal identifier (id) and a value. The acceptors only accept a proposal if it has a proposal id greater than the proposals they have already accepted and if the values are the same.
- The algorithm has two phases: Phase 1: A proposer chooses a proposal number and sends a prepare request to a majority of acceptors. Every acceptor replies if it accepts the proposal and sets the value that should be used based on the previous condition
- Phase 2: If the proposer receives a response from a majority of acceptors, then it sends an accept message to with the proposal number and a value that is the highest among values it received.
- Acceptors send notifications to the learners to disseminate the value that has been chosen. To reduce the number of messages, we could elect a distinguished learner who propagates messages to other learners.
- The election could fail if there are two proposers who keep increment the proposal numbers one after the other, thereby hindering progress. However the safety of the algorithm is still not affected.
Trade-offs/Influence:
- The Paxos algorithm has been influential in the design of distributed systems built for datacenters. Used in systems like Chubby and ZooKeeper, Paxos has a wide range of applications like leader election, distributed locks etc.
This paper presents the Paxos algorithm in plain English. The Paxos algorithm solves the problem of reaching consensus in a distributed system where agents may fail and messages may be dropped or delayed.
Main points:
- The Paxos algorithm has three main roles for agents: Proposers, Acceptors and Learners. These agents behave according to a set of rules prescribed by the algorithm.
- Every proposal that is sent has a proposal identifier (id) and a value. The acceptors only accept a proposal if it has a proposal id greater than the proposals they have already accepted and if the values are the same.
- The algorithm has two phases: Phase 1: A proposer chooses a proposal number and sends a prepare request to a majority of acceptors. Every acceptor replies if it accepts the proposal and sets the value that should be used based on the previous condition
- Phase 2: If the proposer receives a response from a majority of acceptors, then it sends an accept message to with the proposal number and a value that is the highest among values it received.
- Acceptors send notifications to the learners to disseminate the value that has been chosen. To reduce the number of messages, we could elect a distinguished learner who propagates messages to other learners.
- The election could fail if there are two proposers who keep increment the proposal numbers one after the other, thereby hindering progress. However the safety of the algorithm is still not affected.
Trade-offs/Influence:
- The Paxos algorithm has been influential in the design of distributed systems built for datacenters. Used in systems like Chubby and ZooKeeper, Paxos has a wide range of applications like leader election, distributed locks etc.
