Glossary of Terms
By Pritesh Yadav 7 min read —
- Acceptor
- A Paxos role. Acceptors are the voting members; a value is chosen only when a majority of acceptors accept it. They remember the highest proposal number they have promised and the last value they accepted.
- AppendEntries
- The Raft RPC the leader sends to followers to replicate new log entries. With an empty entry list it doubles as the heartbeat that keeps the leader's authority alive and resets follower election timeouts.
- Agreement
- The consensus safety property that no two correct nodes ever decide different values. There is one outcome, not several.
- Ballot (ballot number)
- Paxos's term for a globally ordered, unique proposal number used to rank competing proposals. The Paxos equivalent of Raft's term / epoch.
- Byzantine Fault Tolerance (BFT)
- Tolerance of nodes that behave arbitrarily or maliciously — lying, sending conflicting messages — not just crashing. Raft and classic Paxos assume non-Byzantine (crash-only) faults; BFT needs different, more expensive algorithms.
- Candidate
- A Raft server state. A follower that times out waiting for a leader becomes a candidate, increments the term, votes for itself, and asks others for votes via RequestVote.
- Commit index
- The index of the highest log entry known to be committed. Once an entry is committed it is durable and safe to apply to the state machine; this index only moves forward.
- Committed entry
- A log entry that has been stored on a majority of servers by the current leader. Committed entries will never be lost and will eventually appear, in the same position, on every node.
- Consensus
- The problem of getting multiple nodes to agree on a single value or a single ordering of events, despite failures and an unreliable network.
- Election timeout
- The randomized interval a Raft follower waits without hearing from a leader before starting an election. Randomization spreads out timeouts so candidates rarely clash, avoiding repeated split votes.
- EPaxos (Egalitarian Paxos)
- A leaderless Paxos variant where any node can commit commands; non-conflicting commands commit in one round trip with no fixed leader, improving latency and balance at the cost of complexity.
- Epoch
- Another name for term/ballot — a monotonically increasing number marking a leadership "reign." Used in ZAB and many systems to detect and reject stale leaders.
- FLP (impossibility result)
- Fischer, Lynch & Paterson's theorem: in a fully asynchronous system with even one possible crash, no deterministic algorithm can guarantee consensus is always reached. Real systems sidestep it with timeouts/randomization to get practical (not theoretically perfect) liveness.
- Follower
- The default, passive Raft state. Followers do nothing on their own — they respond to RequestVote and AppendEntries from candidates and leaders.
- Heartbeat
- A periodic empty AppendEntries from the leader that says "I'm still here," suppressing follower election timeouts and preserving the single-leader invariant.
- Joint consensus
- Raft's safe membership-change mechanism. The cluster passes through a transitional configuration that requires majorities from both the old and new member sets, so no moment exists where two disjoint majorities could each elect a leader.
- Leader
- The single Raft server, elected for a term, that handles all client writes and is the sole source of log entries. All changes flow leader → followers.
- Leader completeness
- A Raft safety property: any entry committed in a given term is present in the logs of all leaders of later terms. The voting rules ensure only an up-to-date server can win, so committed history is never lost.
- Learner
- A Paxos role that finds out which value was chosen and acts on it, without participating in voting. In real systems a learner often catches up the application/state machine.
- Liveness
- The guarantee that something good eventually happens — e.g. a decision is reached and progress is made. Contrast with safety. FLP limits liveness guarantees under full asynchrony.
- Log / log entry
- The ordered, append-only sequence of commands each node stores. A log entry holds a command plus the term in which it was created; agreeing on the log is how nodes stay identical.
- Log matching
- A Raft property: if two logs contain an entry with the same index and term, then the logs are identical in all entries up to that point. This lets a follower's log be repaired by a simple backward consistency check.
- Majority (quorum)
- More than half the nodes. Because any two majorities must overlap in at least one node, requiring a majority for every decision guarantees decisions can't conflict. See Quorum.
- Multi-Paxos
- Paxos optimized for a continuous stream of decisions: elect a stable leader once, then skip the prepare phase for subsequent slots, so steady-state commits take a single round trip. This is what real "Paxos" deployments use.
- PBFT (Practical Byzantine Fault Tolerance)
- A landmark BFT consensus protocol tolerating up to f malicious nodes out of 3f+1, via multiple voting rounds. The basis for many later blockchain/permissioned-ledger algorithms.
- Paxos
- Lamport's original consensus algorithm. A single run ("Single-Decree Paxos") agrees on one value via two phases (prepare/promise, then accept/accepted) among proposers and acceptors.
- Prepare / Promise (Phase 1)
- Paxos phase one: a proposer asks acceptors to "promise" not to accept any lower-numbered proposal; acceptors reply with a promise plus any value they've already accepted, so the proposer respects existing choices.
- Accept / Accepted (Phase 2)
- Paxos phase two: the proposer asks acceptors to accept a specific value; if a majority accept, the value is chosen.
- Proposer
- A Paxos role that drives the protocol — picks a ballot number and proposes a value, trying to get a majority of acceptors to accept it.
- Quorum
- The minimum set of nodes whose agreement counts as the cluster's decision — almost always a strict majority. The overlap property of quorums is what makes consensus safe.
- Raft
- A consensus algorithm designed for understandability. It decomposes consensus into leader election, log replication, and safety, with a strong single leader. Behind etcd, Consul, CockroachDB, and more.
- Replicated State Machine (RSM)
- The core pattern: identical state machines on each node that, fed the same commands in the same order, stay in lockstep. Consensus is used to agree on that command order.
- RequestVote
- The Raft RPC a candidate sends to gather votes during an election. A server grants its vote only if it hasn't voted this term and the candidate's log is at least as up-to-date as its own.
- Safety
- The guarantee that nothing bad ever happens — e.g. two nodes never commit different values at the same log position. Consensus protocols hold safety even during partitions; they may pause liveness instead of risking it.
- Snapshot
- A compacted image of the state machine at a point in time, used to discard old log entries (log compaction) and to fast-forward a lagging or newly added server.
- Split vote
- An election where no candidate wins a majority because votes were divided, so a new election must run. Randomized election timeouts make repeated split votes rare.
- Term
- Raft's logical clock: a monotonically increasing number identifying one leadership period. At most one leader exists per term; higher terms always win over lower ones, exposing stale leaders.
- Termination
- The consensus liveness property that every correct node eventually decides — the algorithm doesn't run forever. Bounded by FLP in fully asynchronous models.
- Validity
- The consensus property that the value decided must be one actually proposed by some node — you can't agree on a value nobody asked for.
- ZAB (ZooKeeper Atomic Broadcast)
- The leader-based atomic-broadcast protocol behind Apache ZooKeeper. Like Raft, it uses a single leader and epochs to deliver a totally ordered, replicated log of updates.