Skip to content

CONCEPT Cited by 1 source

Rumor-mongering (gossip)

Rumor-mongering (a.k.a. the dissemination protocol) is the gossip family in which each new update is treated as a rumor that peers re-share until it is "heard enough times" — at which point it is retired. Coined in Demers et al. 1987 as the sibling of anti-entropy.

Mechanism

  1. A node receives or originates a new update; the update becomes a hot rumor.
  2. Each gossip cycle the node pushes hot rumors to fanout random peers.
  3. A rumor is retired (marked removed) after some criterion — e.g. a counter of rounds, or the fraction of peers that already know it — to cap total traffic.
  4. Retired rumors stop being propagated. Anything that still hasn't reached a node is caught later by anti-entropy.

Performance character

"The rumor-mongering cycle occurs relatively more frequently than anti-entropy cycles and floods the network with the worst-case load" (Source: sources/2023-07-16-highscalability-gossip-protocol-explained). However, "the rumor-mongering model utilizes fewer resources such as network bandwidth as only the latest updates are transferred across nodes." The trade is peak-bandwidth-per-round is higher but cumulative bandwidth is lower because retired rumors stop paying cost.

"There is usually a high probability that a message will reach all the nodes" — but not certainty. Rumors can die out on islands of the membership graph. This is why most production stacks pair it with anti-entropy for completeness.

Retirement criteria (from the literature)

  • Blind counter — stop after k rounds.
  • Feedback — stop after k consecutive rounds where the peer already knew the rumor.
  • Counter-and-feedback — combination.

Tuning these directly sets the residue (fraction of nodes that miss the rumor) vs total traffic trade-off.

When rumor-mongering alone is enough

Rumor-mongering suffices when:

  • Updates are idempotent or commutative (last-write-wins).
  • Residue is acceptable (a minority of nodes being stale is tolerable temporarily).
  • Anti-entropy can run at a slower cadence to eventually cover edge cases.

SWIM-style membership protocols use rumor-mongering (piggybacked on ping/ack messages) to propagate join/leave/suspect events quickly; full-membership reconciliation is the slower backstop.

Seen in

Last updated · 319 distilled / 1,201 read