Gossip Protocol - Wikantik

Gossip protocols (epidemic algorithms) propagate information through a cluster via periodic, pairwise state exchanges. They are the standard for decentralized membership and failure detection in large-scale systems (Cassandra, Consul, Dynamo).

Mathematical Model: Infection Rate

Information spread in a gossip network follows the logic of a viral infection. In a cluster of $N$ nodes, if each node gossips with $k$ random neighbors every $T$ seconds, the time to achieve full convergence ( $t_{conv}$ ) is:

t_{conv} \propto \frac{\log(N)}{\log(k)}

Gossip is highly resilient: even if$50% $of nodes fail, the rumor still reaches all surviving nodes with$ O(\log N)$latency.

Protocol Variants

Push: Node A sends its state to Node B. (Fastest for new data).
Pull: Node A requests state from Node B. (Most efficient for catch-up).
Push-Pull: Bidirectional exchange. (Optimal convergence, higher bandwidth).

Use Cases

1. Membership management (SWIM)

SWIM (Scalable Weakly-consistent Infection-style Membership) decouples failure detection from membership updates.

Indirect Probing: If Node A cannot ping Node B, it asks Node C to ping Node B. This eliminates false positives caused by flapping network links between A and B.

2. Failure Detection (Phi Accrual)

Instead of a binary "Up/Down" state, nodes track the inter-arrival time of heartbeats.

$\phi$ (Phi): A value representing the probability that a node has failed.
Benefit: Allows applications to decide their own threshold (e.g., "Wait longer before re-sharding data, but stop routing traffic immediately").

3. State Propagation

Propagating configuration or ring topology. Implementation (Pseudo-Code):

def gossip_round(local_state):
    # Pick k random peers
    peers = random.sample(cluster_nodes, k)
    for peer in peers:
        # Push-Pull: Send what I know, ask what they know
        remote_delta = peer.exchange(local_state.summary())
        local_state.merge(remote_delta)

Comparison: Gossip vs. Consensus

Metric	Gossip (Epidemic)	Consensus (Raft/Paxos)
Consistency	Eventual	Strong (Linearizable)
Scalability	$10,000+ $nodes \|$ <100$nodes
Coordination	Peer-to-peer	Leader-based
Typical Use	Failure detection, metadata	Transactions, locks

Operational Risks

Gossip Storms: If $k$ or $T$ is misconfigured, the network can be saturated with heartbeat traffic.
Partition Sensitivity: In a "split brain," both partitions will maintain their own membership lists. Anti-entropy (periodic full-state sync) is required to heal.
Stale Metadata: Garbage collection of "tombstones" (records of deleted nodes) is necessary to prevent membership lists from growing infinitely.