What Is Consensus in Distributed Systems?
Learn consensus in distributed systems — Raft, Paxos, quorums, and the FLP result — explained with examples and interview questions.
Expected Interview Answer
Consensus is the problem of getting a set of distributed nodes to agree on a single value despite some nodes failing or messages being delayed, solved in practice by algorithms like Paxos and Raft that tolerate crash failures while guaranteeing safety (never agreeing on two different values) and, under favorable conditions, liveness (eventually agreeing on one).
Consensus must satisfy agreement (all correct nodes decide the same value), validity (the decided value was actually proposed by some node), and termination (every correct node eventually decides), and the FLP impossibility result proves no fully asynchronous algorithm can guarantee all three deterministically if even one node can fail, so practical systems rely on randomization, timeouts, or partial synchrony assumptions to make progress. Raft simplifies the classic Paxos protocol into an understandable model: a cluster elects a single leader via randomized election timeouts, the leader appends entries to a replicated log and only commits an entry once it has been replicated to a majority of nodes, and if the leader fails, a new election happens after a timeout, with the newly elected leader guaranteed (via the election restriction) to already hold all previously committed entries. Consensus underpins leader election, distributed locking services, and replicated state machines, and requires a majority (quorum) of nodes to be alive and reachable, which is why systems are typically deployed with an odd number of nodes (3 or 5) to survive minority failures while still forming a majority.
- Provides agreement despite node crashes and network delays
- Raft/Paxos underpin replicated logs used by distributed databases and lock services
- Majority quorums tolerate minority failures while guaranteeing safety
- Explains why odd cluster sizes (3, 5) are standard in production systems
AI Mentor Explanation
Consensus is like a panel of umpires who must all agree on a single decision after a close run-out, even if one umpire’s radio link drops momentarily. In a Raft-like process, the panel elects a lead umpire through a quick show of hands whenever the current lead is unreachable, and a ruling only becomes official once a majority of umpires have confirmed it, so even if one umpire is late or offline, the decision still stands as long as more than half agreed.
Step-by-Step Explanation
Step 1
Leader election
A node times out waiting to hear from a leader, becomes a candidate, and requests votes; it becomes leader if it wins a majority.
Step 2
Log replication
The leader appends client requests to its log and sends AppendEntries messages to replicate them to follower nodes.
Step 3
Commit on majority
Once a majority of nodes have persisted the entry, the leader marks it committed and applies it to the state machine.
Step 4
Failure recovery
If the leader crashes, followers time out and hold a new election; the election restriction ensures the new leader has all committed entries.
What Interviewer Expects
- Definition covering agreement, validity, and termination
- Awareness of the FLP impossibility result and why practical systems use timeouts
- Correct high-level description of leader election and majority-quorum commit in Raft
- Explanation of why odd cluster sizes (3, 5) are used in production
Common Mistakes
- Confusing consensus with simple majority voting without failure handling
- Not knowing why a majority (not all) of nodes is required to commit
- Assuming Paxos/Raft can tolerate malicious (Byzantine) nodes, not just crashes
- Ignoring the FLP result and claiming perfect deterministic consensus is always achievable
Best Answer (HR Friendly)
“Consensus is how a group of machines agree on one answer even when some of them might crash or go quiet at any time. In practice, systems like Raft elect a temporary leader to coordinate, and a decision only becomes official once more than half the machines have confirmed it, so the system keeps working correctly even if a few machines are down.”
Code Example
#define CLUSTER_SIZE 5
#define MAJORITY ((CLUSTER_SIZE / 2) + 1)
int ack_count = 0;
void on_append_entries_ack(int follower_id) {
ack_count++;
if (ack_count >= MAJORITY) {
commit_log_entry(); /* safe: a majority persisted the entry */
apply_to_state_machine();
}
}
void start_election_timeout(void) {
if (no_heartbeat_from_leader()) {
become_candidate();
request_votes(); /* need MAJORITY votes to become leader */
}
}Follow-up Questions
- What does the FLP impossibility result say about asynchronous consensus?
- How does Raft's election restriction prevent losing committed entries?
- What is the difference between Paxos and Raft in practice?
- How does Byzantine fault-tolerant consensus differ from crash-fault-tolerant consensus?
MCQ Practice
1. What three properties must a correct consensus algorithm satisfy?
Consensus requires agreement (same decided value), validity (a value actually proposed), and termination (every correct node eventually decides).
2. Why are consensus clusters typically deployed with an odd number of nodes like 3 or 5?
An odd cluster size gives the best fault tolerance per node — e.g., 5 nodes tolerate 2 failures with the same majority requirement as 6 nodes, without the extra node.
3. What does the FLP impossibility result state?
FLP proves that in a purely asynchronous model with no timing assumptions, deterministic consensus cannot be guaranteed if even a single process may fail, which is why real systems use timeouts and partial synchrony.
Flash Cards
What is consensus in distributed systems? — Getting distributed nodes to agree on a single value despite failures, satisfying agreement, validity, and termination.
What does Raft use to pick a leader? — Randomized election timeouts; a candidate becomes leader after winning a majority of votes.
When is a Raft log entry committed? — Once it has been replicated to a majority of nodes in the cluster.
What does the FLP result imply for practical systems? — Perfect deterministic asynchronous consensus is impossible, so real systems rely on timeouts and partial synchrony.