n candidates each pick one of T timeout slots at random, and the round is clean when exactly one of them holds the earliest occupied slot. Summing over which slot that is gives P(clean) = Σ n(1/T)((T − j)/T)^(n−1), and the expected number of rounds is its reciprocal. At five candidates and ten slots that is 15333/20000 and 1.3044 rounds; at T = 1 — a fixed timeout — it is exactly zero, for ever.
Core ideas
A definition of what has to happen, a sum over the one free choice, and the geometric argument that turns a probability into a wait.
Every follower that times out becomes a candidate and asks for votes. If two candidates start at the same instant they each collect part of the cluster and neither reaches a majority, so the term ends with no leader and everyone tries again. What makes a round clean is not that one candidate wins by argument, it is that one candidate started before all the others.
Condition on the winner's slot j: there are n choices of who the winner is, probability 1/T that this candidate picked slot j, and ((T − j)/T)^(n−1) that every other candidate picked a strictly later slot. The events for different j are disjoint, so the probabilities add, and the sum telescopes into nothing simpler — which is why the lab lists the terms rather than a closed form.
Each round redraws every candidate's slot, so the number of rounds until the first clean one is geometric with success probability P and has expectation 1/P. At P = 15333/20000 that is 1.3044 rounds — the randomisation costs about a third of an extra election, which is a small price for the certainty it buys.
The material
What a split vote is, the sum that prices a clean round, and what happens to the same arithmetic when the timeout is not random at all.
In an election round, each of n candidates waits a randomly chosen timeout and then stands. The round is clean if exactly one candidate holds the earliest chosen timeout, and a split vote otherwise: two or more candidates stand together, divide the votes, and no one reaches a majority.
Modelling the timeout as one of T equally likely discrete slots is a simplification of a continuous random delay, and it is the simplification that makes the probability exactly computable. T is roughly the width of the randomisation window divided by the round-trip time — the resolution at which two candidates can still tell each other apart.
Nearly half the mass sits in the first two terms, which is the shape to carry away: a clean round is usually won early, because winning late requires every other candidate to have chosen later still, and that gets rapidly less likely. The last term is zero because a candidate in the final slot cannot have everyone else strictly after it.
That is the whole argument for randomising the timeout, and it is not a matter of degree. A deterministic timeout does not make split votes likely, it makes them certain, and no amount of retrying helps because every retry reproduces the tie. The randomisation is what makes the expectation finite at all.
Doubling the window from T = 10 to T = 20 raises the clean probability from 76.665% to 87.9166% and lowers the expected rounds from 1.3044 to 1.1374. But each round now waits up to twenty slots instead of ten, so the expected time to elect can go up even as the expected number of rounds goes down. The quantity to minimise is rounds multiplied by the length of a round, and it has an interior optimum — which is why real implementations pick a window of a few multiples of the round-trip time and not the largest one they can get away with.
Three assumptions are doing work here and each is worth naming. All n candidates are assumed to start their timers at the same moment, which is the worst case and roughly what a leader crash produces; slots are assumed discrete and uniform, where a real implementation draws from a continuous range; and every follower is assumed to become a candidate, where in practice one that has already granted a vote or heard from a new leader stands down. All three make the computed P(clean) pessimistic, which is the safe direction for a number you are sizing a timeout with.
Interactive
The probability of a clean first round, and the rounds it takes
Method
The window is the only free parameter and it is traded against the length of a round, not against correctness.
After a leader crash every remaining node may time out, so n is cluster size − 1 at worst. Using a smaller n because “they will not all stand” is how a window gets sized for a case that is not the one it exists for.
T is the randomisation range divided by the resolution at which two candidates' starts can be told apart — in practice, the round-trip time. A window of 150 to 300 milliseconds with a 15 ms round trip is about ten slots.
P(clean) = Σ n(1/T)((T − j)/T)^(n−1) over j, then 1/P rounds. Both are exact and both are small sums; there is no reason to simulate this.
Expected rounds falls as T rises and the duration of a round rises with it. The product is what a user waits, and the window that minimises it is usually a few round trips wide rather than as wide as possible.
A five-node cluster loses its leader. Every remaining node times out and stands. The implementation randomises the timeout across ten distinguishable slots, and the question is how long a leaderless period to expect — and what would happen if the randomisation were removed.
Three quarters of first rounds succeed, and the expectation of 1.3044 says the cost of the remainder is about a third of one extra election. For a window of a few hundred milliseconds that is a leaderless period measured in fractions of a second, which is what makes randomised timeouts a solved problem rather than a tuning exercise.
The T = 1 line is the one to remember, because a fixed timeout is not a worse choice on a spectrum — it is a broken one. Its clean probability is exactly zero and every retry is identical to the last, so the cluster sits in a loop of split votes until something perturbs the timing by accident. Systems have shipped like this and the symptom is a cluster that elects instantly in testing, where clocks and loads differ, and never elects on identical hardware under identical load.
For a faded rehearsal, take the same window to a nine-node cluster, so n = 8 candidates and T = 10. The supplied first move is that the exponent becomes 7, so the j = 1 term is 8/10 · (9/10)⁷. Predict whether P(clean) rises or falls against the five-candidate case before computing it, then compute it, then say what T would restore the original expected rounds.
You should be able to write the clean-round sum from the definition, evaluate it term by term as exact fractions, take the reciprocal for expected rounds, state what happens at T = 1 and why, and name the three modelling assumptions and which direction each biases the answer.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.