Abstract Paxos: Unifying Paxos and Raft through Formal Derivation of Distributed Consensus

The article begins by motivating the need for a unified view of distributed consensus protocols, noting that interview questions often ask about the differences between Paxos and Raft.

It defines the fundamental problem of achieving strong consistency in a distributed storage system, introducing Shannon's information definition (information eliminates randomness) and the concepts of read and write operations that must be deterministic.

Quorum is introduced as a set of nodes sufficient for reads and writes; any two quorums must intersect to guarantee that a committed value is visible to all readers.

Commit is defined as a state that can always be read; three commit conditions are identified: (1) write to a quorum, (2) uniqueness of the committed state, and (3) immutability after commit.

Because a simple log list provides only a partial order, the article adds a commit_index to each log entry, creating a total order on states based on (commit_index, log.length) . Writers must generate a commit_index larger than any known index to avoid livelock, while smaller indices lead to deadlock.

The protocol is split into two phases. Phase‑1 (including sub‑phases 1.1 and 1.2) ensures that no smaller state can be committed by having writers obtain acknowledgments from a quorum that reject any lower commit_index . Phase‑2 writes the new state to a quorum, guaranteeing that the state is the largest and thus uniquely readable.

Implementation details cover incremental state replication, snapshot transfer, and handling of member changes via configuration logs. Config logs define cluster membership and quorum sets; joint configurations must overlap with the previous configuration to avoid split‑brain scenarios.

Two lemmas prove that overlapping configurations prevent simultaneous commits under different configs, and that new configs must be committed on the joint config before proceeding.

The article then shows how abstract‑paxos maps to classic Paxos (single‑log entry, integer commit_index as ballot) and to Raft (term and voted‑for tuple, log entries ordered by (term, index) ), highlighting Raft's simplifications and potential optimizations.

Finally, it discusses possible extensions such as allowing multiple leaders per term, earlier commits, and more flexible member changes, noting that some of these ideas are already explored in projects like openraft.