Two halves that never mix: safety and liveness
Why can no timeout value break a correct protocol's safety?
This split reorganizes this whole mechanism, and it is the most useful idea to keep.
- A safety property says "nothing bad ever happens" (for example, "two leaders never exist in the same epoch").
- A liveness property says "something good eventually happens" (for example, "a leader is eventually elected").
Safety is preserved by intersection arguments, which contain no time. Two majorities of the same set must share a member. This is the pigeonhole argument, with no clock and no assumption about delay. The rule R + W > N (read quorum size plus write quorum size greater than the number of replicas) is the same argument: any set of R replicas that you read from must overlap any set of W replicas that acknowledged the write. A leader elected by a quorum cannot coexist with another leader elected for the same epoch, because the member in the intersection would have had to vote twice. None of this is weakened by an arbitrarily slow network.
Liveness is preserved by timeouts, which are nothing but time. Election timeouts, heartbeat intervals, failure-detector thresholds and lease durations all belong here.
From this follows a design rule, and a test you can apply to every mechanism:
Set the election timeout of Raft (a consensus algorithm, explained in Consensus) to 5 ms and you get constant spurious elections and terrible availability. You do not get two leaders. If you find a mechanism where changing a timeout can corrupt data, you have found a mechanism whose safety depends on a clock. There is exactly one important family of those: leases (time-limited rights). That is why fencing tokens exist. A lease makes safety depend on a bound on clock drift (the rate at which a clock runs fast or slow). A fencing token makes safety depend on a counter that only goes up. It converts a timing argument into an ordering argument. Order is cheaper to agree on than time, and this trade appears three or four times here.
Why liveness cannot be had for free is the FLP result: with no bound on delay, no protocol can guarantee both. Every real system keeps safety unconditional and buys liveness with an assumption about the network (The model you are implicitly choosing).