Membership, reconfiguration and discovery
Why must membership change one member at a time, and why may discovery be stale?
These are two things with different correctness classes, and they are often listed as one.
Membership
Membership is the set over which quorums are computed. It is small, it changes rarely, and it must be agreed. The reason is that quorum intersection is an argument about a known set, and two nodes with different beliefs about that set can form two disjoint majorities without any partition at all. This is split brain by arithmetic, not by network.
There are exactly two safe fixes, and both are intersection arguments.
- Joint consensus. During the transition, decisions must obtain majorities in both configurations (old and new).
- Single-member changes. A majority of N and a majority of N+1 always intersect, since ⌈(N+1)/2⌉ + ⌈(N+2)/2⌉ > N+1. If you add or remove one node at a time, the problem disappears. Check: N = 3, majority 2; N+1 = 4, majority 3; 2 + 3 = 5 > 4. For N = 4 (majority 3) to N+1 = 5 (majority 3): 3 + 3 = 6 > 5.
Reconfiguration belongs right here. A disproportionate share of real consensus bugs has historically lived in it, because it is the one operation whose correctness argument is about two membership sets rather than one.
Discovery
Discovery (where to reach a member) is large, changes often, and is allowed to be stale, because a wrong endpoint yields a failed connection and a retry, not a violated invariant. So it is a cache, with all the properties of caches, including the one that matters most: it is a cache you cannot invalidate. Its TTL is the only instrument, and the destination must be prepared to reject a misdirected request.
The design rule that falls out:
Systems that put shard ownership in DNS learn this the expensive way.
Compression: membership is a quorum-defining set that must be agreed and changed one element at a time; discovery is a stale cache whose errors are retryable, and confusing them is how split brain gets manufactured without a partition.