Computer Science
Grade 12
20 min
Distributed Consensus: Paxos and Raft Algorithms
Study distributed consensus algorithms like Paxos and Raft, which enable nodes in a distributed system to agree on a single value, even in the presence of failures.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define the problem of distributed consensus and explain its importance in fault-tolerant systems.
Describe the key roles and phases of the Paxos algorithm (Proposer, Acceptor, Learner).
Explain the core components of the Raft algorithm: leader election, log replication, and safety.
Trace the execution of a Raft leader election in a small cluster of nodes.
Trace the process of log replication in Raft after a client request.
Compare and contrast the design philosophies and understandability of Paxos and Raft.
Calculate the quorum size required for a given number of nodes to prevent split-brain scenarios.
Ever wondered how a cloud database stays consistent, or how you and your friends can edit a Google Doc at the same time without corrupting it? 🤔 That ma...
2
Key Concepts & Vocabulary
TermDefinitionExample
Distributed ConsensusA fundamental problem in distributed computing where a group of processes (or nodes) must agree on a single data value or a sequence of states. This agreement must be reached even if some processes fail or messages are delayed.Three servers need to decide who the primary database is. They run a consensus algorithm to all agree that 'Server B' is the primary, and this decision is final.
Fault ToleranceThe property that enables a system to continue operating properly in the event of the failure of some of its components. In distributed systems, this often means surviving node crashes or network partitions.A 5-node cluster can tolerate the failure of 2 nodes and still reach consensus and serve requests, because the remaining 3 nodes form a...
3
Core Syntax & Patterns
Raft Leader Election Process
1. Start as Follower. 2. If election timeout elapses, become Candidate. 3. Increment term, vote for self, and send RequestVote RPCs to all other nodes. 4. If votes received from a majority (quorum), become Leader. 5. If another node becomes Leader, step down to Follower.
This is the state transition flow for how a single leader is chosen in a Raft cluster. It ensures that at most one leader can exist in any given term.
Paxos Two-Phase Commit (Simplified)
Phase 1 (Prepare/Promise): A Proposer sends a 'Prepare' request with a proposal number N. Acceptors 'Promise' not to accept any proposal numbered less than N. Phase 2 (Propose/Accept): If the Proposer receives a quorum of Promises, it sends an 'Accept' request with num...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
In a 5-node Raft cluster, an election begins in Term 5. Candidate A gets 2 votes (itself and one other). Candidate B gets 2 votes (itself and one other). The 5th node was slow and didn't vote. What is the most likely immediate outcome?
A.split vote occurs, no leader is elected, and a new election will begin in Term 6 after a new timeout.
B.The candidate with the lower node ID (e.g., A) wins the tie and becomes leader.
C.The cluster remains without a leader indefinitely until a node is manually restarted.
D.Both A and B become leaders, resulting in a 'split-brain' scenario.
Challenging
A 5-node Raft cluster has a stable leader. A network partition separates the leader and one follower (Partition 1) from the other three followers (Partition 2). According to the 'Fault Scenario Reasoning' skill, what will happen?
A.The original leader in Partition 1 continues to operate normally, as it still sees one follower.
B.The entire cluster halts because no partition has a majority of the original 5 nodes.
C.The three followers in Partition 2 will elect a new leader, and the old leader in Partition 1 will eventually step down.
D.Two leaders will exist, one in each partition, causing data inconsistency.
Challenging
In Paxos, why is it critical that in Phase 1, an Acceptor promises not to accept any proposals with a number *lower* than the one it is promising, 'n'?
A.To ensure that proposals are processed in a strictly sequential order.
B.To reduce network traffic by filtering out old, irrelevant messages.
C.To allow multiple proposers to agree on a value simultaneously.
D.To prevent a new Proposer from overwriting a value that might have already been chosen by a majority in a previous, lower-numbered proposal.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing FreeMore from Distributed Systems: Architectures, Concurrency, and Fault Tolerance
Introduction to Distributed Systems: Concepts and Challenges
Distributed System Architectures: Client-Server, Peer-to-Peer, and Cloud-Based
Concurrency Control: Locks, Semaphores, and Monitors
Fault Tolerance: Redundancy, Replication, and Checkpointing
Distributed Databases: CAP Theorem and Consistency Models