SWIM: membership by merge

Ownership and Raft both spend a majority round trip to get one authoritative answer. SWIM does not try to agree on anything. Every node keeps its own view of who else is alive, the views disagree constantly, and the only promise is that disagreements resolve rather than compound.

That is a different kind of promise, bought a different way: by an algebraic property of a merge rule, not by quorum intersection and not by structure.

The record and the rule

A member record is an incarnation number and a status: Alive, Suspect or Dead. Two records are compared by a key: a higher incarnation always wins, and at equal incarnations the more-dead status wins. merge keeps whichever side has the larger key. That is the entire rule.

A probe timeout or a self-refutation is not a different rule. Each is only a different choice of which record arrived:

• A probe that times out makes the node believe the peer Suspect, at the incarnation it had recorded when the probe began. The incarnation is an argument and is not re-read, because a probe is slow and a refutation can land while it is in flight. A suspicion at the old incarnation then loses to the refutation and changes nothing.
• A node that hears it is accused answers with a record one incarnation higher. Alive at a higher incarnation beats suspect and dead at the accusation’s.

What is proved

The claims are S1 to S14 in the Reference. In words:

Idempotence and absorbing a repeat are what let gossip’s real delivery model, at least once and arbitrarily duplicated, survive contact with merge at all. Commutativity and associativity are what make order not matter. S5 is what those add up to once lifted through every step of an execution: not that gossip arrives in order, or even that it arrives, only that whatever arrives never makes a view less accurate than it was.

What is not modelled

• No probe scheduler, no indirect-ping fallback, no dissemination budget. The model is the merge rule and one transition. How often to probe, and what to piggyback, is not modelled, so nothing here says gossip eventually arrives.
• No memberlist-style rejoin handshake. A graceful departure is Left, which out-ranks a failure verdict at the same incarnation. A member that comes back is an ordinary node that hears it is gone and refutes with a higher incarnation, exactly as after Dead. Memberlist gives a rejoin its own rules; here there are none.
• Nothing is forgotten. A departed or dead member’s record is kept, because it is what stops a stale report from reviving it, and it counts against the same bound on members. A cluster that churns through many identities will fill it.
• A node writes nothing down. Incarnations are self-correcting: a restarted node begins at 0, and the first peer to tell it what the cluster believes about it out-ranks its record and is answered with a higher incarnation. A restart costs a round trip, not correctness.

The service

Node is the shell around a verified table: the roster, the lock, the audit log, the batch limit and the order a batch is applied in are plain Rust that the tests exercise. Suspecting a peer, declaring it dead and refuting an accusation are not on the wire. They are things a node does about its own view, and putting them on the wire would let any caller make this node believe anything. A node suspects a peer because its own probe failed.

Who is in the cluster is the roster, and it can be closed or grow. Node::new builds a closed cluster: the members are the ones it was given, and a batch naming anyone else is refused. Node::admitting builds one that grows, with an admission policy, a function from a caller’s address to the member number that address may be. There is no join call. A join is the first ping or sync from an address the policy lets in; the sync reply is the whole table, so the newcomer learns who is there; and the others hear of it by gossip. The member number comes from the policy and the connection, never from the request. To leave, a node calls leave, which records it as Left and hands back that record to tell the peers. A node that is stopped without doing so is, to the cluster, a node that died, and the two are different records.

What this does not settle is who should be admitted. SWIM says nothing about that, and the example’s policy lets in every loopback address. Where a member lives is the deployment’s mapping from member number to address, not something SWIM gossips. A live member keeps one address; one that has left or died may come back from a different one, which replaces the old. And a cluster trusts its members: any one can fill the bound on members with made-up numbers.

How it relates to the rest

SWIM is independent of the other protocols in the proofs. It is related to them in one direction, and only as a hint:

• Ownership assumes failure detection is unreliable, and survives a revoke of a healthy node. SWIM’s Suspect and Dead are exactly that kind of signal.
• The actor system reads a SWIM view to decide where not to place new work and which addresses to stop returning. It never uses it to decide an actor has moved. That is the ownership epoch’s job.

The SWIM rows are in the Reference’s SWIM section.

Next: the actor, which sits on ownership.