A distributed system has five nodes (IDs 1–5). Node 3 suspects the leader has crashed and initiates a Bully election. Node 5 eventually wins. Later, due to a network partition, node 3 also declares itself leader. What property of leader election has been violated?
ALiveness — the system failed to elect a leader quickly enough
BSafety — at most one leader must exist at any time, but now two exist
CFairness — the highest-ID node should always win, but node 3 won instead
DTermination — the election did not complete within a bounded time
The core safety requirement of leader election is that at most one leader exists at any time. Having two simultaneous leaders — a 'split brain' — allows conflicting decisions (e.g., both accept conflicting writes), leading to data corruption. This is categorically different from having no leader (which hurts availability but is recoverable). Liveness concerns whether an election eventually completes; fairness is not a formal property; termination is a liveness property.
Question 2 Multiple Choice
The Bully algorithm generates O(n²) messages in the worst case. Why does this happen?
AEach node broadcasts to all others simultaneously, and all n nodes do this independently
BThe node with the lowest ID initiates, and each higher-ID node passes the baton to the next, requiring n rounds
CMultiple nodes can detect the leader's failure and each initiates an election, sending messages to all nodes with higher IDs
DThe algorithm requires two full ring traversals to confirm the elected leader
In the worst case, all n nodes simultaneously detect the leader's failure and each initiates an election. Node i sends election messages to all nodes with IDs higher than i. Node 1 sends n−1 messages, node 2 sends n−2, and so on — summing to O(n²) total messages. The ring traversal description applies to the Ring algorithm, not Bully.
Question 3 True / False
Randomized election timeouts (as used in Raft) make it very unlikely that two nodes start elections simultaneously, but cannot guarantee it never happens.
TTrue
FFalse
Answer: True
This is the honest tradeoff of randomization. By having each node wait a random duration before starting an election, the probability of simultaneous starts is very low but nonzero. The Raft paper explicitly acknowledges that split votes can occur and handles them by starting a new election term. This probabilistic approach is accepted in practice because split votes are rare and self-correcting — they do not produce a split brain, they just delay the election.
Question 4 True / False
In the Ring algorithm, the node with the highest ID generally wins because it sends the most messages around the ring.
TTrue
FFalse
Answer: False
The highest-ID node wins not because of message volume but because the election message accumulates IDs as it travels the ring, and the node with the maximum ID in the completed message is declared leader. All nodes contribute one ID to the message; the winner is determined by the maximum value, not the number of messages sent. Every node contributes exactly one append operation.
Question 5 Short Answer
Why is preventing 'split brain' considered more critical than guaranteeing that an election always completes quickly?
Think about your answer, then reveal below.
Model answer: Split brain (two simultaneous leaders) allows both leaders to make conflicting decisions — accepting different writes, assigning conflicting tasks — producing data corruption or state divergence that may be impossible to reconcile. Having no leader only blocks progress temporarily, which is recoverable. Safety (at most one leader) is preserved even if the system is slow to elect; violating it can cause permanent data loss or inconsistency.
This reflects the CAP theorem intuition: most systems prioritize consistency (safety) over availability (liveness). A system with no leader is unavailable but correct; a system with two leaders is available but produces incorrect results. In practice, systems like Raft are designed so that network partitions may make the minority partition unavailable (no quorum, no leader) rather than allowing it to elect its own leader and diverge.