hesela.devPaxos
Paxos is a consensus protocol for choosing a single proposed value despite non-Byzantine process failures and unreliable message delivery.
A proposer first obtains promises and prior accepted proposals, then submits the required value for acceptance. It must retain the value from the highest-numbered accepted proposal in its phase-1 responses, if any. A chosen value and a value merely accepted by one node are different states. [1]
Crash recovery requires acceptors to retain promises and accepted-proposal state before replying. Quorum counts do not independently verify that this storage obligation was met. [1]
Multi-Paxos applies consensus to a sequence of slots and amortizes phase 1 across slots under a stable leader. A competing higher proposal can prevent that leader from progressing. Safety and eventual progress are separate properties. [1]
Flexible Paxos separates the phase-1 and phase-2 quorum families while preserving cross-phase intersection. It does not replace the promise and value-selection rules. [2]
Relations
Citations
- Leslie Lamport. Paxos Made Simple (2001), sections 2-3.
- Howard, Malkhi and Spiegelman. Flexible Paxos: Quorum Intersection Revisited. OPODIS 2016, LIPIcs 70 (2017), sections 3-7.
Further reading
Sources & caveats
- Protocol semantics, not a device lifecycle; status is unknown and firstSeen is unset rather than assigning an invention date from a later explanatory paper.