Cluster Membership: A Belief, Not a Fact

Membership rests entirely on failure detection, and failure detection over an asynchronous network is provably imperfect: no algorithm can distinguish a crashed process from a slow one, because both look identical — silence (No Heartbeat Does Not Mean Dead, Crashed or Just Slow: The Distinction You Cannot Make).

So "is B in the cluster?" has no observer-independent answer. A believes B is gone, C believes B is present, and B believes it is fine and is still serving requests from clients who can reach it. All three are reasoning correctly from what they observe. There is no oracle to appeal to, and building one is exactly the impossibility.

What a system can do is impose an *ordering* on beliefs, so that although nobody knows the truth, everybody eventually agrees on the same story. That is what consensus-backed membership buys: not accuracy, but agreement. A node may be wrongly evicted, but every node agrees it was evicted, at the same point in the sequence, and downstream decisions built on that sequence stay consistent with one another.

That distinction — accuracy versus agreement — is the whole of this lesson. You cannot buy accuracy. You can buy agreement, and it costs a majority.

Almost every membership design mistake comes from using one mechanism for two purposes with very different requirements. Split them and the choice becomes obvious.

Membership for routing answers "where should I send this request?" A wrong answer costs a failed request and a retry. It may be eventually consistent, gossiped, cached and stale, because being wrong is cheap and self-correcting — the request fails, the client retries elsewhere.

Membership for correctness answers "who may act?" Who is in the quorum. Who may be leader. Who holds the lock. Who owns this partition. A wrong answer here is not a retry, it is two writers, a split brain, or a lost write. This membership must be totally ordered, and every action taken under it must carry the configuration version so that a stale actor can be recognised and refused (Fencing Tokens: Making the Stale Actor Safe, Not Just Unlikely, Terms and Epochs: Making Stale Leaders Harmless).

The failure of the naive design is precise: gossip the membership, then let quorum composition follow it. Under partition, both sides gossip themselves into a view in which they hold a majority, and both proceed (Split-Brain: Two Nodes, Both Certain They Are In Charge). No amount of tuning fixes this; only an ordered configuration change does.

The practical consequence is a hybrid, and it is what mature systems run: a small consensus group owns the authoritative configuration and changes it rarely, while gossip distributes fast, approximate liveness for routing. See Coordination Services: The Primitives, Not the Product for the first half and Gossip: Epidemic Spread Instead of Everyone Telling Everyone for the second.

Failure gets the attention; joining is where the subtler bugs live.

Bootstrap split-brain. Five nodes start simultaneously. A network hiccup means nodes 1–2 see only each other and nodes 3–5 see only each other. If "form a cluster with whoever you can see" is the rule, you now have two clusters with the same name, each accepting writes, each entirely convinced it is *the* cluster. They will not merge later; their histories have diverged.

The fix is that bootstrap must be an explicit, one-time, externally-specified act: name the initial members (--initial-cluster), or require an expected size before forming, or have exactly one node bootstrap and every other node *join* an existing cluster. This is why every serious system makes first-boot awkward. The awkwardness is the safety.

Rejoining is not the same as joining. A node that restarts has lost its volatile state but may have stale durable state. If it rejoins under the same identity, old rumours about it — "B is alive at version 7" — can resurrect a stale view, and old rumours against it — "B is suspect" — can immediately re-evict a healthy process. The standard fix is an incarnation number (Cassandra calls it a generation): a counter, persisted or derived from a start timestamp, that increases on every restart. Statements about a node are tagged with the incarnation they refer to, so a rumour about incarnation 7 has no effect on incarnation 8. Without it, a flapping node produces membership chaos out of proportion to its actual behaviour.

The related mechanism is refutation: when B learns that others suspect it, it broadcasts a higher incarnation of itself, which supersedes the suspicion. This is how SWIM lets a wrongly-suspected node rescue itself in one round instead of being evicted and having to rejoin. It works precisely because it is B — the only party with direct evidence of B’s liveness — that gets to speak.

Leaving gracefully is categorically different from failing. A graceful leave is an announcement: unambiguous, immediate, requiring no inference. A failure is an inference: ambiguous, delayed, sometimes wrong. Make shutdown always announce, and the vast majority of membership events stop being guesses.

If membership determines quorums, then changing membership changes what a quorum *is* — and doing it carelessly breaks the overlap property that quorums depend on.

The classic hazard: move from a 3-node cluster {A,B,C} to a 5-node cluster {A,B,C,D,E} in one step. Suppose A and B adopt the new configuration while C has not. Now {A,B} is a majority of the old 3 for C’s purposes... no — more precisely, {C} plus one other can form a majority of the old configuration while {A,B,D,E} forms a majority of the new one, and the two overlap in no node that has both configurations. Two disjoint majorities exist simultaneously, and both can elect a leader. The safety property that made consensus work has been silently removed by a configuration change.

Raft offers two remedies. Single-server changes: add or remove one node at a time, which guarantees the old and new majorities always intersect. Joint consensus: a transitional configuration requiring majorities in both the old and the new set before the new one takes effect. Both work; the first is simpler and is what most implementations use, which is why growing a cluster from three to five is two operations rather than one.

The operational rule that falls out: never change more than one member at a time, and never change membership while the cluster is already degraded. Adding a replacement node during an outage feels helpful and is one of the more reliable ways to lose a quorum permanently.

Consensus-backed membership works well up to a few hundred nodes and is usually deployed with a much smaller quorum group than the cluster it describes — three or five members holding a configuration that names thousands. What does not scale is putting *every* node in the consensus group: every change needs a majority of them, and majority round trips over a large, wide group are slow and fragile.

Gossip-based membership scales to thousands because each node’s cost is constant — a few probes per interval regardless of cluster size (Gossip: Epidemic Spread Instead of Everyone Telling Everyone). What it gives up is exactly what the correctness case needs: ordering and agreement.

The composition that works: a small consensus group holds the authoritative configuration and the ownership assignments; gossip distributes liveness quickly to everyone; the consensus group consumes gossip as *evidence* but makes changes deliberately and slowly, with a delay before acting on suspicion. That delay is what stops the composition from becoming the feedback loop described in Rebalancing: A Load Spike You Schedule for Yourself.