Gossip and failure detectors
How epidemic gossip spreads state in logarithmic rounds, why no failure detector can be perfect, and how phi accrual and SWIM trade detection speed for false suspicion.
30 min7 steps
By the end you can
- Estimate how many rounds epidemic gossip needs to reach a cluster, and why it scales
- Explain completeness and accuracy of failure detectors and why timeouts cannot distinguish slow from dead
- Compute phi accrual suspicion levels and choose a threshold for a detection-speed trade-off
Spreading state without a centre
Logarithmic spread
- 1,000 nodes17 rounds
- 100,000 nodes28 rounds
- 1,000,000 nodes34 rounds
Select push spread, then compare pull spread and pushPull spread in Script.
Loading question…
No failure detector is perfect
Completeness
- Every crash is eventually suspected
Accuracy
- Live nodes are not suspected
Fast timeout
- 500 ms: quick, but wrong on slow nodes
Slow timeout
- 10 s: rarely wrong, slow failover
Phi accrual: a suspicion level, not a verdict
phi
-log10(P late)
phi = 1
10%
chance it is just late
phi = 3
0.1%
chance it is just late
Cassandra default
phi 8
silence / (mean gap x ln 10)
Select phi false positive in Script.
Loading question…
Choosing the threshold
t = 0
Last heartbeat
Low threshold
Suspect early, may be wrong
High threshold
Suspect later, rarely wrong
Jittery network
Mean gap rises, so does the silence needed
Select phi failure detection, then phi false positive in Script.
Loading question…
SWIM: ask someone else before you accuse
Check your mastery
phi
log base 10
mean gap
ln 10
natural log
Score 80% or more. Each false suspicion feeds a needless election in consensus.
Mastery check
5 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
Answer this step to continue.