Gossip and SWIM: probabilistic dissemination with explicit suspicion

Gossip spreads information through repeated peer exchanges. Anti-entropy repeatedly compares state; rumor mongering forwards a fresh rumor for a bounded or probabilistic lifetime. Coverage depends on fanout, rounds, loss, churn, and repair policy, so “all nodes know after k rounds” is not a deterministic guarantee.

SWIM separates failure detection from dissemination. It tries direct ping, then indirect probes, and marks a member suspected before dead. Incarnation numbers let a live member refute stale suspicion. This is weakly consistent membership, not consensus or a linearizable registry.

Prerequisites and model

• Node identities and incarnations survive or change safely across restart.
• Peer sampling avoids permanent topology bias and periodic anti-entropy repairs missed rumors.
• Probe timeouts are tuned from observed networks; one missed ping is not proof of death.

Correctness claims and invariants

• GOS-C1. Epidemic spread is probabilistic; bounded rumor lifetime and loss can leave gaps.
• GOS-C2. Anti-entropy reconciles state repeatedly and is distinct from rumor mongering.
• GOS-C3. SWIM uses direct and indirect probes while disseminating membership separately.
• GOS-C4. Suspicion delays death and a higher incarnation refutes stale suspicion.
• GOS-C5. Partitions create divergent local views; gossip does not authorize one side.
• GOS-C6. Application data still needs versioning, merge, or coordination.

What the scenarios prove

• Randomized rumor spread (rumor-spread): Sampled peers receive a rumor; coverage grows probabilistically.

• Direct SWIM probe (direct-probe): A matching direct acknowledgement completes one probe period.

• Indirect probe (indirect-probe): A direct timeout triggers helper probes before suspicion.

• Suspicion and refutation (suspicion-refute): A live suspected node raises incarnation to supersede suspicion.

• Partition divergence (partition-divergence): Both sides keep local views; gossip cannot choose an authoritative side.

• Missed rumor repair (rumor-loss-repair): A cold rumor can miss Delta; periodic anti-entropy repairs it.

• Application anti-entropy (anti-entropy): Version comparison repairs state but still needs semantic merge.

• Restart incarnation (restart-incarnation): A restarted member publishes strictly newer identity state.

Failure, concurrency, and retry traps

• One missed ping creates false positives under loss or pauses.
• Reusing an old incarnation after restart cannot supersede newer status.
• Bounded rumor dissemination without repair can miss a peer permanently.
• Partitioned sides may suspect each other; neither view is a quorum certificate.

Boundaries and non-guarantees

• Gossip is not consensus, linearizable membership, or safe leader election.
• Convergence time is a distribution and SLO, not a constant round count.
• Membership convergence does not make application updates commutative.

Related material

Primary sources

1. Demers et al., Epidemic Algorithms for Replicated Database Maintenance
2. Das, Gupta, Motivala: SWIM
3. Amazon Dynamo: Highly Available Key-value Store
4. USENIX ATC 2018: Lifeguard