44 - Gossip Protocols & Membership

Previous: 43 - CRDT & Conflict-Free Replication | Next: 45 - Geo-Distributed Systems

---

1. What Is a Gossip Protocol?

A gossip protocol (also called epidemic protocol) is a peer-to-peer communication mechanism where nodes periodically exchange information with randomly selected peers. Like rumors spreading through a crowd, information eventually reaches every node without any central coordinator.

Round 1:  Node A knows info X, picks random peer B
          A -> B: "Hey, I know X"

Round 2:  Both A and B know X, each picks a random peer
          A -> C: "I know X"
          B -> D: "I know X"

Round 3:  A, B, C, D all know X, each picks a random peer
          ... exponential spread ...

After O(log N) rounds: ALL nodes know X

---

2. How Gossip Works

Basic Algorithm

Every T seconds (gossip interval, typically 1-2s):
  1. Select a random peer from the membership list
  2. Exchange information with that peer
  3. Merge received information into local state

Gossip Styles

Push:
  A --[my data]--> B
  B merges A's data into its own

Pull:
  A --[what do you know?]--> B
  B --[my data]--> A
  A merges B's data

Push-Pull:
  A --[my data]--> B
  B --[my data]--> A
  Both merge each other's data (most efficient convergence)

---

3. Convergence Analysis

How fast does information reach all N nodes?

Push gossip with fanout f = 1 (contact 1 random peer per round):

  Round 0: 1 node knows (the originator)
  Round 1: ~2 nodes know
  Round 2: ~4 nodes know
  Round k: ~2^k nodes know

  Convergence: O(log N) rounds for N nodes

With fanout f:
  Round k: ~(1+f)^k nodes know
  Convergence: O(log_f N) rounds

Example: N = 1000 nodes, gossip interval = 1s
  Push-pull with f=1: ~10 rounds = ~10 seconds for all nodes to know
  Push-pull with f=3: ~6 rounds = ~6 seconds

Probability of Convergence

After c * log(N) rounds (c is a constant > 1):
  Probability that ANY node hasn't received info < 1/N^(c-1)

With c=3, N=1000:
  P(some node missed) < 1/1000^2 = 0.000001 = 99.9999% convergence

Interview Tip

The O(log N) convergence is the key selling point. For 1000 nodes, gossip converges in ~10 rounds. For 10,000 nodes, only ~13 rounds. This logarithmic scaling is why gossip works so well in large clusters.

---

4. SWIM Protocol: Failure Detection + Membership

SWIM (Scalable Weakly-consistent Infection-style Process Group Membership) is the most practical gossip protocol for cluster membership. Used by Consul, Serf, and Memberlist.

SWIM Failure Detection

Node A detects if Node B is alive:

  Step 1: Direct Ping
  A --[ping]--> B
  B --[ack]--> A       If ACK received: B is alive. Done.

  Step 2: Indirect Ping (if direct ping fails)
  A --[ping-req(B)]--> C, D, E  (randomly chosen intermediaries)
  C --[ping]--> B
  D --[ping]--> B
  E --[ping]--> B
  
  If any intermediary gets ACK from B -> B is alive
  If none get ACK -> B is SUSPECTED

  Step 3: Suspicion
  B is marked SUSPECT for a configurable timeout
  If B sends any message during suspicion period -> cleared
  If timeout expires -> B declared DEAD, removed from membership

Why Indirect Ping?

Direct ping may fail due to network path issue between A and B specifically:

       A ----X---- B          (direct path broken)
       |           |
       C-----------+          (indirect path works)

Without indirect ping: false positive (B incorrectly declared dead)
With indirect ping: C can reach B, so B is NOT falsely declared dead

---

5. SWIM Membership List

Every node maintains a local membership list. Changes propagate via gossip.

Node A's membership list:
+--------+--------+-----------+
| NodeID | Status | Incarnation|
+--------+--------+-----------+
| A      | ALIVE  | 3          |
| B      | ALIVE  | 5          |
| C      | SUSPECT| 2          |
| D      | DEAD   | 7          |
| E      | ALIVE  | 1          |
+--------+--------+-----------+

Membership events (piggybacked on gossip messages):
  - JOIN: new node announces itself
  - ALIVE: node responds to suspicion (with higher incarnation)
  - SUSPECT: node failed direct + indirect ping
  - DEAD: suspicion timeout expired

Incarnation Numbers

Incarnation numbers prevent stale information from overriding fresh information.

Scenario: Node B was suspected due to temporary network issue.
          B recovers and wants to refute the suspicion.

B increments its incarnation number and broadcasts:
  "I am B, incarnation 6, status ALIVE"

Other nodes: 
  "B's current incarnation in my list is 5, incoming is 6 -> accept ALIVE"

Rule: Higher incarnation always wins. Same incarnation:
  DEAD > SUSPECT > ALIVE (worst status wins for safety)

---

6. Piggybacking: Efficient Dissemination

SWIM piggybacks membership updates onto the ping/ack messages that are already being sent for failure detection. No extra messages needed.

Normal ping:
  A --[ping + {B:SUSPECT, inc:5}]--> C

C processes:
  1. Respond with ACK
  2. Update local membership: mark B as SUSPECT if inc:5 > stored incarnation
  3. Will piggyback this info on its next ping to another node

Result: Membership updates spread at the same rate as failure detection
        with ZERO extra bandwidth cost.

---

7. Full Gossip Protocol Diagram

+----------+        +----------+        +----------+
| Node A   |        | Node B   |        | Node C   |
| Members: |        | Members: |        | Members: |
| A,B,C,D  |        | A,B,C,D  |        | A,B,C,D  |
+----+-----+        +----+-----+        +----+-----+
     |                    |                    |
     |  1. ping(B)        |                    |
     |------------------->|                    |
     |     ack + gossip   |                    |
     |<-------------------|                    |
     |                    |                    |
     |                    | 2. ping(C)         |
     |                    |------------------->|
     |                    |    ack + gossip    |
     |                    |<-------------------|
     |                    |                    |
     | 3. ping(C)         |                    |
     |-------------------------------------->  |
     |          ack + gossip                   |
     |<----------------------------------------|
     |                    |                    |
     |  <<< Round repeats every T seconds >>>  |
     |                    |                    |

If Node D fails:
     |  4. ping(D) -> timeout                  |
     |  5. ping-req(D) to B, C                 |
     |---> B ---> D (no ack)                   |
     |---> C ----------> D (no ack)            |
     |  6. All report failure                  |
     |  7. D marked SUSPECT                    |
     |  8. Suspicion gossips to all nodes      |
     |  9. After timeout: D marked DEAD        |

---

8. Applications in Real Systems

Cassandra

Cassandra uses gossip for:
  - Cluster membership (which nodes are alive)
  - Schema agreement (DDL changes propagate via gossip)
  - Token/range ownership (which node owns which data)
  - Load information (how busy each node is)

Gossip interval: 1 second
Failure detection: Phi Accrual Failure Detector (adaptive threshold)
  - Not binary alive/dead, but a suspicion level (phi value)
  - phi > 8 typically means dead (configurable)

Consul (HashiCorp)

Consul uses SWIM-based gossip via the "memberlist" library:
  - Service discovery across data centers
  - Health checking
  - Event broadcasting

Two gossip pools:
  1. LAN gossip: within a data center (fast, tight timeouts)
  2. WAN gossip: across data centers (higher latency tolerance)

Redis Cluster

Redis Cluster gossip:
  - Cluster bus on port+10000 (e.g., 6379 data, 16379 gossip)
  - Nodes exchange ping/pong messages
  - Each message carries a random subset of known nodes' info
  - Failure detection: majority of master nodes must agree node is down (PFAIL -> FAIL)

---

9. Anti-Entropy with Merkle Trees

Gossip handles recent updates. Anti-entropy repairs long-standing divergence by comparing data between replicas.

Anti-entropy using Merkle trees:

Node A's data:        Node B's data:
  key1: val_a           key1: val_a
  key2: val_b           key2: val_b_new  <-- different!
  key3: val_c           key3: val_c
  key4: val_d           key4: val_d

Merkle tree comparison:

        root                    root
       /    \                  /    \
    H(1,2)  H(3,4)         H(1,2)  H(3,4)
    /   \    /   \          /   \    /   \
  H1   H2  H3   H4       H1   H2' H3   H4

Step 1: Compare roots -> different (H(1,2)+H(3,4) vs H(1,2)+H(3,4))
Step 2: Compare left subtrees -> same (H1,H2 vs H1,H2'... wait)
Step 3: Compare H2 vs H2' -> different!
Step 4: Only sync key2 (not all data)

Result: O(log N) comparisons to find exactly which keys differ

---

10. Consistency of Membership Views

Gossip provides eventual consistency for the membership view. At any given moment, different nodes may have slightly different views.

Example: Node E just joined

  t=0:  Only Node A knows about E (E contacted A to join)
  t=1:  A gossips E's JOIN to Node B
  t=2:  A gossips to C, B gossips to D
  t=3:  All nodes know about E

  During t=0 to t=3:
    - A routes requests to E
    - B,C,D don't know E exists yet
    - This is acceptable for most applications

  Guarantee: EVENTUALLY all nodes will have the same view

When This Matters

---

11. Tuning Parameters

---

12. Comparison: Gossip vs Other Approaches

---

13. Key Trade-offs

---

14. Interview Checklist

• Explained gossip concept (epidemic spreading, random peer selection)
• Described push, pull, push-pull variants
• Analyzed convergence: O(log N) rounds
• Covered SWIM protocol (ping, ping-req, suspicion mechanism)
• Explained incarnation numbers for refuting stale suspicions
• Discussed piggybacking for efficient dissemination
• Named real systems using gossip (Cassandra, Consul, Redis Cluster)
• Described anti-entropy with Merkle trees
• Addressed consistency of membership views (eventual)
• Compared gossip with centralized heartbeat and consensus approaches

---

15. Resources

• Paper: "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol" (Das et al., 2002)
• Paper: "Epidemic Algorithms for Replicated Database Maintenance" (Demers et al., 1987)
• Book: "Designing Data-Intensive Applications" (Kleppmann) -- Chapter 5
• HashiCorp Memberlist -- github.com/hashicorp/memberlist (Go SWIM implementation)
• Cassandra Documentation -- Gossip section
• YouTube: Martin Kleppmann -- "Distributed Systems" lecture series (Cambridge)
• Blog: Ably -- "Understanding Gossip Protocols"

---

Previous: 43 - CRDT & Conflict-Free Replication | Next: 45 - Geo-Distributed Systems