Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 36 ยท Building Blocks

Gossip Protocols and Probabilistic Structures

See how gossip spreads data through a cluster in about log n rounds, and how Bloom filters and HyperLogLog sketches keep that traffic small.

How do you tell a thousand machines something without a central announcer? You could send the message to all of them, but then the sender is a bottleneck and a single point of failure. Gossip takes the same approach as office rumors: each node tells a few random peers, those peers tell a few others, and soon everyone knows.

Gossip is simple, robust and surprisingly fast. It powers membership lists, failure detection, configuration spread and anti-entropy repair in systems such as Cassandra, Consul and many Dynamo-style stores. In this lesson you will simulate it, measure how long it takes, and then meet two probabilistic structures, the Bloom filter and HyperLogLog, which keep gossip messages tiny. If you have not yet seen how nodes detect each other's failures, Failure Detectors and Heartbeats shows a close relative of this idea.

Gossip in one minute

Pick a peer Every round, choose a random node.
Exchange Send news, ask for news, or both.
Repeat Everyone learns within a few rounds.

No coordinator, no single point of failure.

1 / 2

Epidemic dissemination

Gossip is also called epidemic dissemination because the math is the same as for a spreading infection. A node that holds a new update is infected. In each round it contacts random peers and infects them. Three styles exist:

  • Push: an infected node sends the update to a random peer.
  • Pull: every node asks a random peer, "anything new?" and copies what it learns.
  • Push-pull: both directions in a single exchange.

Early on, the number of infected nodes roughly doubles each round, so spreading is exponential. That is why a cluster of thousands is covered in a few dozen rounds at most. The simulation below starts with one informed node out of 64 and prints how many know the update after every round.

Python Push gossip, round by round

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the shape: a fast doubling phase, then a long tail. Once most nodes are informed, a random peer is usually already informed, so the last few stragglers can take many rounds to be hit. Pure push is great at the start and slow at the end. Pull behaves the other way round: when most nodes know the news, a random question almost always finds it.

How many rounds does it take?

Rounds grow roughly with the logarithm of the cluster size, plus a tail. Doubling the cluster adds only a few rounds, not twice as many. You can also trade bandwidth for speed with a higher fanout, the number of peers contacted per round, or with push-pull.

Python Rounds versus cluster size, fanout and style

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The exact numbers depend on the seeds, but the pattern holds. Going from 16 to 1,024 nodes (64 times larger) costs only about ten extra rounds. Push-pull beats both single directions, which is why real systems often exchange summaries both ways.

Two practical points:

  • Gossip is probabilistic. There is no hard guarantee that one round delivers to everyone, only a very high probability after enough rounds. Systems mix gossip with a slower, exact repair mechanism.
  • Gossip tolerates failure naturally. A crashed node simply stops being picked; a dropped message is made up for by a later round. That is the same message-loss reality discussed in The Fallacies of Distributed Computing.

What do nodes actually gossip?

Gossip carries different things depending on the job:

  • Membership: "I have heard from nodes A, B, C recently, and D has not answered in a while."
  • State and metadata: schema versions, ring ownership, load figures.
  • Data summaries for anti-entropy: a compact description of what a replica holds, so peers can find and fix differences. This ties back to the conflict handling in Multi-Leader and Leaderless Replication.

Sending a full list of a million keys every second would defeat the point. Instead, nodes gossip summaries, and that is where probabilistic structures help.

Bloom filters: "have you seen this?"

A Bloom filter is a bit array plus a few hash functions. To add an item, you hash it several times and set those bit positions. To query, you check whether all those bits are set. If any bit is zero, the item is definitely absent. If all are set, the item is probably present. Bloom filters give false positives but never false negatives. The data-structure details are covered in Bloom Filters.

In a distributed system, a replica can send a small Bloom filter of the keys it holds. A peer checks its own keys against that summary and sends only those that the filter says are absent. A false positive means one key is skipped this time, and the next round of anti-entropy will catch it with a different filter or different hash seeds.

Python A Bloom filter as an anti-entropy summary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the "skipped by mistake" line. A key is skipped only when a false positive hides it, which can happen but is rare with a filter this size. In this run all 20 keys that B lacks were sent. The 64-byte summary stands in for a list of 40 key names.

A plain Bloom filter cannot delete items, and it fills up as you add more. Real systems size it for the expected number of items and rebuild it periodically, or use variants such as counting or cuckoo filters.

HyperLogLog: "how many different ones?"

Sometimes the question is not "do you have X" but "roughly how many distinct things have we seen?" For example, the number of distinct users hitting a service across fifty servers. Counting exactly needs to ship every ID around. HyperLogLog (HLL) estimates the number of distinct items with a few hundred small registers.

The idea: hash each item to a random bit string. A hash that starts with many zeros is rare, like flipping many heads in a row. If the longest run of leading zeros you have seen is 10, you have probably seen on the order of 2^10 distinct items. To reduce the variance, HLL splits items into buckets by the first hash bits and averages the evidence from all buckets.

What makes HLL perfect for distributed systems is the merge: take the register-wise maximum of two sketches and you get the sketch of the union. Merging is commutative, associative and idempotent, so it works under gossip with duplicates and any message order. This is the same property that CRDTs rely on.

Python Estimating distinct users with mergeable sketches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two nodes overlap on 2,000 users. A plain sum would double count them (12,000), but the merged sketch lands near the true 10,000 because the overlap sets the same registers. With 256 registers the typical error is around 6.5%; more registers give a better estimate at a linear memory cost.

Choosing the right tool

Which structure fits?

Gossip Spread a fact to everyone cheaply.
Bloom filter Ask "probably present?" with tiny messages.
HyperLogLog Estimate distinct counts and merge anywhere.

All three trade a little exactness for a lot of scale.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Roughly how does the number of gossip rounds grow with cluster size?

    Informed nodes roughly double each round at first, so doubling the cluster adds only a few rounds.
  2. 2. Why does pure push gossip have a long tail at the end?

    Once most nodes know the update, a random push usually lands on a node that already has it. Pull and push-pull fix this.
  3. 3. A Bloom filter reports that an item is absent. What do you know?

    Bloom filters have no false negatives: at least one of the item's bits is zero, so it was never added.
  4. 4. What property of HyperLogLog sketches makes them suitable for gossip?

    Max-merge is commutative, associative and idempotent, so duplicates and reordering do not change the result.

Summary

  • Gossip spreads information by having each node repeatedly contact random peers; there is no coordinator.
  • Spreading takes about log n rounds plus a tail; push-pull and higher fanout shorten it.
  • Gossip is probabilistic, so systems pair it with exact repair.
  • Bloom filters give compact "probably present" summaries with false positives but no false negatives.
  • HyperLogLog estimates distinct counts and merges with a register-wise maximum, so it works under duplicated, reordered gossip.

Next, learn how services survive slow and failing dependencies in Resilience Patterns.