Skip to content

PATTERN Cited by 1 source

Push-pull gossip

Push-pull gossip is the gossip spread strategy in which, on each round, a node sends its known updates to a random peer and simultaneously requests the peer's updates — so each exchange is bidirectional.

It is not a third kind of gossip next to push and pull — it is the empirical winner of the three, because it gets the best of each regime.

The three strategies

From sources/2023-07-16-highscalability-gossip-protocol-explained:

  • Push model — the node with a fresh update pushes it to a random subset. "efficient when there are only a few update messages" — early in spread, most nodes don't know the update, so a push almost always lands on a node that needs it.
  • Pull model — every node actively polls random peers for updates. "efficient when there are many update messages" — late in spread, most nodes do have the update, so a pull almost always lands on a node that can deliver it.
  • Push-pull — both in one exchange. "optimal to disseminate update messages quickly and reliably. The push approach is efficient during the initial phase when there are only a very few nodes with update messages. The pull approach is efficient during the final phase when there are numerous nodes with many update messages."

The canonical analysis: push has O(log N) rounds but a constant-probability failure tail; pull has a small constant extra round; push-pull combines them into O(log log N) tail convergence — near-optimal. (See Demers et al. 1987 and Karp/Schindelhauer 2000 for the derivation.)

Shape

Node A                             Node B
  |                                  |
  | --- my state digest +  ------->  |
  |     known-new updates            |
  |                                  |
  |  <--- your state digest + -----  |
  |       known-new updates          |
  |                                  |
  |  --- updates you asked --->      |
  |      for in your digest          |
  |                                  |
  |  <--- updates I asked -------    |
  |       for in my digest           |

Cassandra's three-message gossip round (SYN, ACK, ACK2) is exactly this shape: SYN carries A's digest, ACK returns B's digest + the updates A needs, ACK2 returns the updates B still needed after seeing A's digest.

When push-only or pull-only is enough

  • Write-heavy, rapid convergence requirement → push-pull (default).
  • Rare, batch-style updates → push only is fine — the spread finishes before the pull advantage kicks in.
  • Slow, long-tail repair → pull only (or anti-entropy); no one is pushing but slow read-repair picks up stragglers.

Applicability across gossip families

"The strategies to spread a message apply to both anti-entropy and rumor-mongering models" (Source: sources/2023-07-16-highscalability-gossip-protocol-explained). Push-pull is orthogonal to the dataset-shape choice between concepts/anti-entropy and concepts/rumor-mongering.

Seen in

Last updated · 319 distilled / 1,201 read