Distributed systems contain multiple machines that must sometimes agree on:
This is the problem of distributed coordination.
A simple application can often make decisions inside one process:
Application
│
└── one memory spaceA distributed system looks like:
Node A
Node B
Node C
Node DNow there is no single shared memory space and no perfectly reliable communication channel.
Coordination becomes difficult because:
A node cannot always distinguish a crashed node from a slow node or a broken network connection.
This chapter develops the concepts needed to reason about coordination safely.
Imagine a scheduled job:
Every minute:
generate daily reportYou have 10 application instances:
A
B
C
D
E
F
G
H
I
JIf every instance executes the job:
10 reportsmay be generated instead of:
1 reportYou need coordination:
Coordinator
/ | \
/ | \
A B C
...Only one worker should own the task at a time.
Distributed coordination appears in:
Consider two servers:
A ───────── BA sends:
Are you alive?No response.
What does that mean?
Possibilities:
1. B crashed
2. B is overloaded
3. Network is slow
4. Network path is broken
5. B received the message but response was lost
6. B is alive but cannot communicateA cannot know the exact reason from silence alone.
This is one of the fundamental difficulties of distributed systems.
A distributed system often uses:
Example:
A ── heartbeat ──► B
A ◄─ heartbeat ── BIf heartbeats stop:
timeout
↓
suspect BNotice the wording:
suspect
not:
prove that B crashed
Failure detection is often based on incomplete information.
A heartbeat is a periodic signal indicating that a node is alive.
Example:
Every 5 seconds:
Node A → coordinator:
"I'm alive"If the coordinator does not receive heartbeats:
5 sec
10 sec
15 sec
↓
Node A suspected unavailableHeartbeat frequency is a trade-off.
Too frequent:
More network traffic
More processingToo infrequent:
Slow failure detectionA heartbeat usually answers:
Is the process communicating?
A health check can answer something more meaningful:
Is the application healthy enough to receive traffic?For example:
Process alive ✓
Database connection ✗
Disk full ✗
Dependency unavailable ✗A process can be alive but not healthy.
Therefore production systems often distinguish:
A common coordination problem is:
Which node is the leader?
Example:
Node A
Node B
Node CThe system needs:
Leader = AOther nodes become followers.
Leader A
/ \
B CThe leader may coordinate:
Suppose the leader crashes:
Leader A ✗
B
CThe system needs another leader:
Leader B
/ \
A CWithout a safe election mechanism, multiple nodes may believe they are leader.
That creates split brain.
Split brain occurs when different parts of a distributed system independently believe they are authoritative.
Example:
Network Partition
A B
│ │
│ │
"I am leader" "I am leader"Now:
Client 1 → A
Client 2 → BBoth leaders may accept conflicting writes.
This can corrupt state.
Suppose:
Node A
term = 10
leader = trueNetwork partition occurs.
A continues running.
Meanwhile:
Node B + Celect B as the new leader:
term = 11A may still think:
"I am leader."Therefore leadership must be associated with a mechanism that lets the system reject stale leaders.
This leads to terms, epochs, leases, and fencing tokens.
A leader can have a monotonically increasing term:
Leader A
term = 10New election:
Leader B
term = 11Any message from the old leader:
term = 10can be recognized as stale.
The system can reject it when the current term is:
11This is a powerful defense against stale leadership.
A fencing token is a monotonically increasing number associated with ownership.
Example:
Worker A:
token = 100
Worker B:
token = 101If B becomes the new owner, downstream storage can require:
token >= current tokenThen:
A sends token 100
↓
Storage
↓
REJECTwhile:
B sends token 101
↓
Storage
↓
ACCEPTThis prevents stale workers from performing dangerous operations.
Suppose only one worker should process:
job = 123A distributed lock can provide:
Worker A
│
▼
LOCK(job:123)
│
▼
Process jobAnother worker:
Worker B
│
▼
LOCK(job:123)
│
▼
Rejected / waitsBut implementing safe distributed locks is much harder than implementing a local mutex.
Process
┌──────────────┐
│ Mutex │
│ Thread A │
│ Thread B │
└──────────────┘One memory space.
Node A ───── Network ───── Node B
\ /
LockNow failures can happen between acquisition and use.
The lock holder can crash.
The network can partition.
A delayed process can wake up later.
These problems require additional safeguards.
A distributed lock often has an expiration:
LOCK
TTL = 30 secondsIf the worker crashes:
30 seconds
↓
lock expires
↓
another worker can acquire itThis prevents permanently abandoned locks.
But TTL creates a subtle problem.
Suppose:
Worker A
lease = 30 secondsA acquires the lock.
Then A pauses for:
40 secondsThe lease expires.
Worker B acquires the lock:
B = ownerA wakes up.
Now:
A thinks it owns lock
B actually owns lockBoth can execute.
This is why a lease alone may not be sufficient for safety.
Suppose every lock acquisition returns a fencing token.
First:
Worker A
token = 10Later:
Worker B
token = 11Storage remembers:
highest token = 11A wakes up and sends:
WRITE(token=10)Storage rejects it:
10 < 11B sends:
WRITE(token=11)Storage accepts it.
This is much safer than relying only on lock expiration.
Long-running workers can renew a lease:
Acquire lease
↓
Work
↓
Renew
↓
Work
↓
RenewIf renewal fails:
Stop processingA robust design should ensure the worker stops making protected writes after losing ownership.
Leader election is closely related to consensus.
Consensus means that distributed nodes agree on a value or decision despite failures.
A consensus system typically needs to reason about:
Protocols such as:
are used to solve consensus problems under defined failure assumptions.
Imagine:
A
B
CThe nodes need to agree:
leader = BA safe consensus protocol aims to ensure that correct nodes do not permanently commit conflicting decisions.
Conceptually:
Proposal
↓
Agreement
↓
CommitThe exact mechanics depend on the protocol.
A quorum is a sufficient subset of nodes required for a decision.
For:
N = 5a majority quorum is:
3because:
3 > 5/2Two different majorities must overlap.
For example:
Quorum A:
1, 2, 3
Quorum B:
3, 4, 5They overlap at:
Node 3This overlap is fundamental to many consensus systems.
Suppose a cluster has:
5 nodesIf the system requires:
3 votesthen at most:
2 nodescan be unavailable while a majority still exists.
A ✓
B ✓
C ✓
D ✗
E ✗Majority remains:
3The cluster can continue making decisions if the protocol permits it.
Suppose:
Partition 1:
A
B
Partition 2:
C
D
EOnly the side with:
3 nodeshas a majority.
The 2-node side cannot safely commit decisions that require majority agreement.
This prevents both partitions from independently becoming authoritative.
This creates an important relationship:
5-node cluster
Partition:
2 nodes | 3 nodesThe majority side can potentially continue.
The minority side may need to stop certain operations.
This is a coordination mechanism for avoiding split brain.
Raft is a consensus algorithm designed to be understandable and practical.
It organizes nodes into roles:
Leader
Follower
CandidateNormally:
Leader
/ \
Follower FollowerClients send writes to the leader.
The leader replicates entries to followers.
If followers stop receiving heartbeats:
Leader
Xone follower may become a candidate.
It increments its term and requests votes.
Candidate B
│
├──► A: vote?
└──► C: vote?If it receives a majority:
B = LeaderThis is a simplified view; actual Raft includes detailed rules for terms, logs, voting, and election safety.
Raft uses monotonically increasing terms.
Example:
Term 5:
Leader A
Leader fails
Term 6:
Leader BA message from term 5 can be recognized as older than term 6.
This helps prevent stale leaders from remaining authoritative.
Suppose the leader receives:
SET X = 20The leader appends a log entry:
Log:
1 → SET X=10
2 → SET X=20It replicates the entry to followers.
Once the appropriate majority condition is satisfied, the entry can become committed according to Raft's rules.
Followers then apply the committed entry to their state machines.
A useful consensus mental model is:
Client command
↓
Consensus log
↓
Replicated log
↓
State machineEach correct node applies the same committed commands in the same order.
Therefore:
Node A state
Node B state
Node C statecan remain consistent.
Replication means:
copy data to multiple nodesConsensus means:
agree on the order/decisionYou can have replication without strong consensus.
Consensus protocols combine agreement and replication to maintain a consistent replicated state under specified failures.
Paxos is another family of consensus algorithms.
At a high level, Paxos deals with:
Paxos is historically important and foundational in distributed systems.
Its descriptions can be difficult to follow, so for practical system-design interviews, it is often more useful to understand:
Why consensus exists
What quorum means
How leaders are elected
How committed state is replicated
What failures are toleratedbefore diving into the complete protocol mechanics.
| Aspect | Raft | Paxos |
|---|---|---|
| Goal | Consensus | Consensus |
| Teaching | Designed for understandability | Often more abstract |
| Leader-based structure | Yes | Common variants use leadership |
| Terms/epochs | Yes | Uses proposal/ballot numbering |
| Log replication | Explicit | Multi-Paxos commonly used |
| Interview value | High practical value | Important foundational concept |
Do not treat one as universally "better."
They are different consensus approaches.
Many systems use dedicated coordination systems rather than implementing consensus independently inside every application.
Historically/common examples include:
They can support capabilities such as:
The exact features and consistency semantics depend on the system and configuration.
A coordination service can provide a shared namespace:
/config/payment
/config/inventory
/leader/order-service
/locks/job-123Applications can:
create
read
update
watchcoordination state.
This avoids forcing every application team to implement its own coordination protocol.
Some coordination systems support ephemeral registrations.
Conceptually:
Node A
│
▼
register /services/api/AIf A disappears or its session expires:
/services/api/Acan disappear automatically.
This can help service discovery and leader election.
Suppose:
API Gatewayneeds to find:
Payment ServiceInstead of hard-coding:
10.0.0.5it can query service discovery:
payment-service
↓
10.0.0.5
10.0.0.6
10.0.0.7The registry tracks service instances.
What happens if the registry is unavailable?
A good architecture should avoid making every request depend synchronously on the registry.
Possible approaches:
Coordination systems themselves become critical infrastructure and therefore need high availability.
A coordination service can also store configuration:
/config/service-a/database-url
/config/service-a/timeout
/config/service-a/feature-xServices can watch for changes.
Example:
Configuration updated
↓
Watch event
↓
Service reloads configurationCare must be taken with:
A distributed cluster needs to know:
Who is currently part of the cluster?Example:
A ✓
B ✓
C ✓
D ✗Membership systems track nodes and their status.
But again:
"Node D is not responding" does not necessarily prove D is dead.
Membership systems therefore need failure detection rules and timeouts.
Suppose:
heartbeat interval = 5 sec
timeout = 15 secA temporary network delay of:
16 seccould cause a healthy node to be suspected.
If timeout is too short:
false positives ↑If timeout is too long:
failure detection slowsThere is no perfect timeout.
Distributed coordination also encounters time problems.
Each machine has its own clock:
Node A: 10:00:00.100
Node B: 10:00:00.080
Node C: 10:00:00.130Clocks can differ due to:
Therefore wall-clock time should not automatically be treated as a perfect ordering mechanism.
Distributed systems can use logical clocks to represent ordering.
Instead of asking:
What physical time did this happen?we can ask:
What happened before what?Lamport clocks provide a simple mechanism for representing causal ordering.
Each process maintains:
counterBefore a local event:
counter++When sending:
send counterWhen receiving:
counter = max(local, received) + 1This creates an ordering relationship.
Important:
A Lamport timestamp can indicate that one event happened before another in the logical ordering, but equal or ordered timestamps alone do not necessarily tell you that two events are causally related in every case.
Vector clocks provide more causal information.
For three nodes:
[A, B, C]Example:
[2, 1, 3]They can help distinguish:
A happened-before Bfrom:
A and B are concurrentThe trade-off is additional metadata.
A lease-based leader mechanism:
Leader
↓
lease expirescan be useful, but a lease by itself does not necessarily solve all distributed consistency problems.
Consensus protocols provide stronger agreement mechanisms under defined failure assumptions.
Use the right abstraction for the problem.
Consider:
Leader A
│
X
network partition
X
│
Nodes B + CB and C elect:
Leader BA still thinks it is leader.
Without fencing/terms/consensus:
A → write
B → writeBoth may modify state.
This is split brain.
Common techniques include:
The design should make stale authority harmless.
This is more important than simply detecting that a node is stale.
One way to reduce conflicts:
Leader
/ | \
A B COnly the leader performs certain writes.
Benefits:
Costs:
Instead of one global leader:
Global Leaderpartition leadership:
Shard 1 → Leader A
Shard 2 → Leader B
Shard 3 → Leader C
Shard 4 → Leader DThis can increase scalability.
Example:
User IDs 0-9999
→ Leader A
10000-19999
→ Leader BEach shard has its own ownership.
Suppose:
Leader A owns:
Shard 1
Shard 2
Shard 3A fails.
The system needs to transfer ownership:
Shard 1 → B
Shard 2 → C
Shard 3 → BThis requires coordination.
Rebalancing should avoid:
Suppose 10 workers process jobs.
Requirement:
Each job should be processed once logically.Possible architecture:
Scheduler
│
▼
Queue
│
┌──┼──┬──┐
▼ ▼ ▼ ▼
W1 W2 W3 W4The queue can provide ownership semantics.
For scheduled jobs without a queue, a distributed lock or leader-based scheduler may be used.
Kubernetes itself relies heavily on distributed coordination.
Conceptually:
Control Plane
│
├── API Server
├── Scheduler
├── Controllers
└── State StoreThe control plane maintains desired state and coordinates cluster changes.
Understanding distributed coordination helps explain:
Distributed databases may use coordination for:
For example:
Leader
│
├── Replica A
├── Replica B
└── Replica CIf the leader fails:
Election
↓
New leader
↓
Replication continuesA powerful distributed-systems distinction:
Nothing bad happens.
Examples:
Never have two valid leaders.
Never commit conflicting state.
Never process stale ownership.Something good eventually happens.
Examples:
Eventually elect a leader.
Eventually process a job.
Eventually recover.A system often trades some liveness to protect safety during uncertain failures.
Suppose the network is partitioned.
A system might choose:
No majority
↓
No new leaderThis reduces availability.
But it protects safety:
No conflicting leadersOnce communication is restored:
majority available
↓
leader election
↓
progress resumesThis is a fundamental distributed-systems trade-off.
A timeout proves that a server crashed.
A timeout only tells us that the expected communication did not complete within the timeout.
The server may be:
A distributed lock with a TTL is automatically safe.
Not necessarily.
A worker can outlive its lease and continue operating.
Fencing tokens or another ownership mechanism may be required.
Leader election alone prevents split brain.
Not necessarily.
You also need a mechanism that prevents stale leaders from continuing to perform authoritative operations.
Examples:
More replicas always improve availability.
Not automatically.
More replicas increase potential redundancy but also increase:
Consensus means every node must respond.
No.
Consensus commonly relies on a quorum.
For:
N = 5a majority may be:
3The remaining two can be unavailable while progress remains possible under the protocol.
Because nodes cannot perfectly distinguish crashes from network delays or partitions. A safe election mechanism must prevent multiple nodes from simultaneously acting as authoritative leaders.
Split brain occurs when different parts of a distributed system independently believe they have authority, such as two nodes both believing they are the leader.
This can cause conflicting writes and state corruption.
A fencing token is a monotonically increasing ownership identifier. Downstream resources reject operations carrying an older token, preventing stale workers or leaders from acting after their ownership has expired.
A quorum ensures that decisions require enough nodes to overlap with other valid quorums. Majority-based quorum prevents two independent partitions from both obtaining majority authority.
A good practical answer:
Both are consensus approaches. Raft was designed with understandability and explicit leader/log concepts in mind, while Paxos is a foundational family of consensus algorithms that is often presented more abstractly. For system design, understand quorum, leader election, terms, replicated logs, commitment, and failure behavior before memorizing protocol details.
A typical leader-based consensus system:
Leader fails
↓
Followers stop receiving heartbeats
↓
Election timeout
↓
Candidate starts election
↓
Majority votes
↓
New leader
↓
Replication resumesThe exact mechanics depend on the protocol.
Requirements:
Design:
Job Store
│
┌──────┴──────┐
│ │
Scheduler A Scheduler B
│ │
└──────┬──────┘
│
WorkersConsider:
Imagine:
5-node cluster
A B C D ECurrent leader:
A
term = 10Partition:
A B | C D EQuestions:
A strong solution should mention:
majority
terms/epochs
fencing
log reconciliationBefore deploying coordination infrastructure, ask:
Think of distributed coordination as:
Many nodes
│
▼
Need shared decision
│
▼
Communication can fail
│
▼
Cannot trust silence
│
▼
Need protocol
│
├── Quorum
├── Terms / epochs
├── Leader election
├── Leases
├── Fencing
└── ConsensusThe goal is not simply:
"Make all nodes agree."
The deeper goal is:
Make distributed decisions safely despite delays, crashes, partitions, and stale participants.
You learned:
The most important takeaway:
In distributed systems, you cannot assume that a missing response means failure. Safe coordination requires explicit mechanisms for authority, quorum, ownership, ordering, and stale-node protection.
Explain why a timeout does not prove a server has crashed.
Design a distributed lock for 5 nodes.
Explain:
Explain split brain with a 5-node cluster.
Why is a majority quorum important?
Explain the difference between:
Replication
vs
ConsensusExplain:
Safety
vs
Livenessusing leader election.
Design leader election for a scheduled-job system.
Next we will move from coordination into high availability.
We will learn:
Mark it as complete to track your mastery.