Pointer Walk

Gossip Protocols

One server knows something. Each round, everyone who knows tells one other at random, and a million servers hear it within a few dozen rounds.

Distributed SystemsIntermediate8 min read

Telling a thousand servers something

A cluster has a thousand servers. One of them notices that a neighbour has died. Every server needs to hear about it.

The obvious design is a central coordinator that keeps the list and tells everyone. It works, until the coordinator is slow, overloaded, or is itself the server that died.

There is another way, and it comes from how rumours spread in an office. Nobody announces anything. One person tells another, those two each tell someone, and by lunch everyone knows.

The protocol

  1. One server learns something

    For example: "server 17 has stopped responding".

  2. At regular intervals, it picks another server at random and tells it

    Any server at all. No list of who has been told is kept.

  3. Every server that knows does the same

    Each one, every round, picks a random server and passes it on.

  4. Repeat

    Until everyone has heard.

That is a gossip protocol, sometimes called an epidemic protocol, because information spreads the way an infection does.

Gossip: each round, tell one server at randomInteractive

Start. 64 servers. One of them has just learned something: a setting changed, or a server died. There is no central list and no boss to announce it.

Round
0
Servers that know
1 / 64
Messages that reached nobody new
0

Why it is so fast

Early on, almost every message reaches a server that had not heard. So the number of servers that know roughly doubles each round: 1, 2, 4, 8, 16.

Doubling is very fast.

ServersRounds until all have heard, roughly
6411
1,00017
1,000,00035

A million servers, and everyone knows within a few dozen rounds. With one round per second, that is about half a minute. Multiplying the cluster by a thousand added only about twice as many rounds.

Why the end is slow

Watch the last rounds in the animation. Most servers already know, so most messages land on someone who has heard it before. The remaining few are only reached by luck.

That is why the totals in the table are a bit more than pure doubling would give. The spread has two phases: fast doubling to reach most servers, then a slower tail to catch the stragglers.

What makes it robust

Gossip looks wasteful. Many messages are repeats. That redundancy is exactly why it is hard to break.

  • No server is special. There is no coordinator to fail. Any server can start a rumour and any server can pass it on.
  • Lost messages do not matter. If one message is dropped, the same news will arrive from someone else a round later.
  • Dead servers do not matter. A message sent to a dead server is wasted, and others carry on.
  • The load is even. Each server sends one message per round, whether the cluster has ten members or a million.

Good at

  • No central point to fail or overload
  • Tolerates lost messages and crashed servers without special handling
  • Each server does a small, fixed amount of work per round
  • Scales to very large clusters

Where it bites

  • Not instant: news takes a number of rounds to reach everyone
  • For a while, different servers believe different things
  • No guarantee about exactly when a particular server will hear
  • Many messages are repeats

Agreeing in the end, not at once

During those rounds, some servers know and some do not. A system built on gossip accepts that. It promises that everyone will agree eventually, not at every instant. This is called eventual consistency.

So gossip is the right tool when being a few seconds out of date is harmless:

  • Who is in the cluster. Which servers are alive, which have joined or left.
  • Failure detection. Servers gossip about who they have heard from recently. If nobody has heard from a server for a while, it is declared dead.
  • Spreading settings and summaries such as load figures.

It is the wrong tool for decisions that everyone must make identically at the same moment, such as who the leader is. Those need a majority vote.

Key takeaways

  • In a gossip protocol, each server periodically tells one random server what it knows.
  • The number of servers that know roughly doubles each round at first.
  • A million servers hear the news in a few dozen rounds.
  • There is no coordinator, and lost messages or dead servers do not stop the spread.
  • Servers agree eventually, not instantly, so gossip suits membership and failure detection, not decisions that need exact agreement.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress