Concepts
Gossip, membership and failure detection
Intuition
Picture a large office with no receptionist and no master staff list. Every so often each person chats with a randomly chosen coworker and they swap notes on who has joined or left the team and what has changed, so news spreads through the whole office without anyone being in charge. To decide whether someone is really gone, some offices simply stop counting on a coworker who ignores their messages (and check back now and then), while others learn how often they usually hear from each person, so the longer the silence compared with that rhythm, the more suspicious they become, acting only when suspicion is high enough.
How it works
In Dynamo there is no central registry of which nodes are alive or which ring positions they own: each node periodically gossips its own ring/membership view to a randomly chosen peer, and the two merge their views. Cassandra's membership is likewise gossip-based, built on Scuttlebutt, which the Cassandra paper describes as a very efficient anti-entropy gossip mechanism, valued for low CPU use; the same gossip also carries other system control state, not only membership. For failure detection, Dynamo's final design does not rely on a gossiped global view (early designs did, but explicit joins/leaves made it unnecessary); its failure detection is purely local: node A treats B as failed when B does not respond to A's messages, even if B answers others, and A periodically retries B to see whether it has recovered. Cassandra instead uses a modified Phi Accrual Failure Detector, which outputs a suspicion level, Phi, rather than a yes-or-no answer, on a scale that adjusts dynamically to network and load conditions, and the paper credits accrual detectors with being very good in both accuracy and speed. Each node keeps a sliding window of inter-arrival times of gossip messages from the other nodes and computes Phi from the resulting distribution; the Cassandra authors found an exponential distribution fit better than the Gaussian approximation suggested by the original accrual paper, because of how the gossip channel affects latency. If a node is suspected when Phi reaches 1, the chance of a mistake (a late message later contradicting the decision) is about 10 percent, falling to about 1 percent at Phi 2 and about 0.1 percent at Phi 3. Membership changes spread by gossip until every node's list agrees, while each node judges failures on its own; neither paper claims zero coordination: Dynamo relies on administrator-issued joins/leaves and seed nodes, and Cassandra's rack-aware and datacenter-aware policies use a Zookeeper-elected leader that tells nodes which ranges they replicate.
In practice
Membership and ring positions spread peer to peer by gossip, so no central service has to be asked on each request, although Cassandra still uses Zookeeper for some coordination such as a leader that assigns replica ranges under its rack- and datacenter-aware policies. The Cassandra paper reports a 100-node experiment in which other detectors took about two minutes to detect a failed node, while the accrual detector with Phi set to 5 brought the average to about 15 seconds. You would choose this approach when you want a detector that is both accurate and fast (the paper's measurement was a single 100-node experiment), accepting that the Phi threshold is a setting you tune against the risk of false suspicions.
Use it in a design
Practice the cases that rely on this concept in the System Design school.