Membership and Failure Detection via Gossip

In one line: every mechanism so far assumes the system knows which nodes exist. Maintaining that view without a central registry — and without overreacting to transient blips — is the last piece of the design.

Why the system is deliberately slow to react

This is a design decision, not an oversight. Reacting instantly to a missing node would mean:

• Recomputing Merkle trees for every affected key range (Lesson 9's cost).
• Moving data to new owners on the ring.
• Doing all of that again in ninety seconds when the node finishes rebooting.

Hinted handoff already keeps the system writable while a node is briefly away, which buys the time to be patient. Node addition and removal in the ring should be performed only after confirming a sustained failure or a planned membership change.

This is the slow-vs-dead problem, answered

The Foundations module established that a slow node and a dead node are indistinguishable from the outside. Most systems treat that as a detection problem to solve with better timeouts.

This design sidesteps it instead: make being wrong cheap. Because hinted handoff covers a node that is merely away, the system does not need to decide quickly — it can afford to wait until the evidence is overwhelming. Designing so that an ambiguous signal has a safe default is usually better than trying to resolve the ambiguity faster.

Membership history and gossip

Planned commissioning and decommissioning of nodes result in membership changes. These are recorded as membership history, which each node persists locally. The ring reconciles that history across nodes using a gossip protocol.

A gossip-based protocol maintains an eventually consistent view of membership. When two nodes randomly choose one another as peers, both efficiently synchronize their persisted membership histories.

How it spreads

Each node keeps a token set — the virtual nodes in the consistent hash space, mapping nodes to their respective token sets, stored locally on disk.

Walking the example: node A starts up and randomly adds nodes B and E to its token set. When A handles a request that results in a change, it communicates that to B and E. Separately, node D has C and E in its token set; it makes a change and tells C and E. Other nodes do the same.

This way, every node eventually knows about every other node's information. It is an efficient way to share information asynchronously, and it does not consume much bandwidth.

Why gossip rather than a coordinator

A central membership registry would be simpler to reason about — and it would be a single point of failure in a design whose entire premise is that no node is special.

Gossip gives an eventually consistent view with no coordinator, no election, and bandwidth that scales gently with cluster size. It fits a system already built on eventual consistency: membership converges the same way data does.

Contrast this with the databases material, where partition-to-node routing used ZooKeeper — a strongly consistent coordination service. Both are valid; the difference is that there, disagreeing about ownership was a correctness bug, whereas here the design already tolerates disagreement and repairs it.

Declaring a node dead

In this decentralized model, nodes explicitly broadcast when they join or leave the ring. If a node fails to communicate with its peers for a predefined time, the peers mark it as dead.

Note the asymmetry: joining and leaving deliberately are announced, while failure is inferred from silence. Announcements are cheap and unambiguous; inference is what needs the patience described above.

Conclusion

A fault-tolerant key-value store must handle both temporary and permanent failures:

Interview signal by level

Next: running the whole design under interview conditions.