Lesson 8: PAXOS and Friends Flashcards
What is the goal of a consensus protocol?
An algorithm that ensures a group of processes in a distributed system can agree on a value of a shared state, and that the value was proposed by one of the participating processes.
What must a consensus protocol must guarantee?
Safety
- only a value that has been proposed is chosen
- only a single value is chosen
- only a chosen value is learnt/read
Liveness
- some proposed value is chosen
- any chosen value is learnt
Note: the FLP theorem said that it’s impossible to have both safety and liveness in a system where there’s a possibility of at least one failure
What roles can a node have in a consensus protocol?
Proposer: propose possible values for the shared state
Acceptor: evaluate proposals and decide which to accept
Learners: need to read the current agreed upon value of the shared state
How does 2-Phase Commit work?
There’s a coordinator and participants. The coordinator proposes a value, the participants vote, the coordinator tallies the votes and then communicates the decision to the participants.
Pros / Cons
+ protocol is simple
+ protocol is safe
- protocol blocks if there are failures => no liveness
How does 3-Phase Commit work?
There’s a pre-prepare phase, a prepare phase, and a decision phase.
Pros / Cons
+ protocol doesn’t block if there are failures => liveness
- assumes fail-stop (once node is dead it stays dead). has safety issues on fail-restart
What assumptions is Paxos built on?
Asynchronous, non-Byzantine model:
- agents operate at arbitrary speed, may fail by stopping, and may restart
- agents have source of persistent memory to remember information after restarting
- messages can take arbitrarily long to be delivered, can be duplicated, lost, or reordered, but cannot be corrupted
What ideas underpin Paxos?
State Machine Replication: each node is a replica of some state machine (algorithm) that captures the state of the system and follows the same set of rules that determine how the state is updated.
Majority Quorum: each decision requires a majority quorum, which guarantees that two quorums have intersecting participants. This makes it safe to disseminate decisions even when some nodes have failed and aren’t participating in a consensus round b/c when they restart and need to catch up their next quorum will at least one participant that had already learned about past agreements. This is necessary for the system to tolerate fail-stop and fail-restart failures.
Ordering: everything is timestamped so it can be ordered. This is necessary for the system to tolerate arbitrary message delays.
What are the three phases in Paxos?
Prepare: a node proposes an agreement round
Accept: the initiator/leader gathers votes on its proposal and if an agreement is reached communicates commit
Learn: agreed upon value can be learnt by all
How does Paxos do on safety and liveness (FLP Theorem)?
Paxos doesn’t guarantee that progress can always be made / it has a possible liveness problem.
If proposals are submitted at the same time we can get into a state where they continually cancel each other out.
Workaround:
- random delays when retrying a new value
- designate a “distinguished proposer” (and some timeouts to resolve leader failure)
What is multi-paxos?
Each “simple” single-decree Paxos used for agreeing on a single value.
Multiple Paxos protocols for agreeing on the order and values of a sequence of operations.
What is RAFT?
Unlike Paxos, RAFT has a distinct leader election phase.
Like Paxos, any node can be a candidate for leader, but only the node that receives the most votes becomes one.
After a leader is elected, the log replication phase starts. The leader makes proposals for updates and replicates the updates to the followers.
By separating the leader election phase from the log replication phase RAFT makes it easier to reason about the behavior of the systƒ2em and keep track of which proposals should be winning proposals or not.
