Convergence Time

How long until ALL nodes converge on the same state?

For random gossip with one peer per round:

• Expected convergence time: O(log N) rounds (Demers et al. 1987 epidemic theorem).
• For N=1000 with 1-second rounds: ~10 seconds.
• For N=10000: ~14 seconds.

Variance: depends on graph properties. With perfect mixing, very tight. With clustering, slower.

Optimizations to speed up:

• Anti-entropy (full state exchange): catches up nodes that missed updates.
• Push-pull: more bandwidth per round but faster convergence.
• Larger fan-out (talk to multiple peers per round): faster but more bandwidth.
• Piggyback: bundle multiple updates per gossip message.

Trade-off: messages per round vs convergence time.

For ULTRA-fast propagation (bitcoin block dispatch, for example): use multi-fan-out with deduplication. Each peer forwards to 8 others. Spreads in milliseconds across thousands of nodes.

Practical numbers: Consul claims ~1s per round, ~10s convergence for 100-node clusters. Cassandra similar. Hashicorp publishes benchmarks for memberlist on their blog.