N seats, one shared airwave. Every tick, some seats whisper to their table-neighbors — but if two neighbors whisper into the same ear at once, it garbles into noise. How fast can a signal make it all the way around the table?
Framed for fun, not felony: think of it as how fast a tell could spread if only one voice at the table can land at a time — the physics of a hard broadcast constraint, not an endorsement of anything shady at your actual game.
Grounded in "A Gossiping Protocol for Sparse Ad-Hoc Radio Networks" — arXiv:2606.29152.
The real finding: in a radio network where nodes only hear direct neighbors and colliding broadcasts are indistinguishable from silence, a deterministic scheduling protocol gets every node's message to every other node ("gossip") in Õ((mn)3/5) time steps on sparse graphs (m edges, n nodes) — beating the previous general ~n4/3 bound. Smart coordination of who talks when beats everyone-talks-whenever contention.Simplification: the paper's protocol discovers the unknown topology on the fly; the "Smart" table below is a graph-coloring round-robin that assumes the seating chart is known upfront. It's a stand-in that demonstrates the same core mechanism — a collision-free transmit rotation — not a literal implementation of the paper's algorithm.
Collision rule
1. Each tick, some seats try to whisper to their table-neighbors (who's "next to" whom is the graph drawn on the felt).
2. A seat hears clearly only if exactly one of its neighbors whispered this tick — and it then learns everything that neighbor currently knows.
3. If two or more neighbors whisper at once, the seat gets garbled noise — worse, it can't even tell a collision happened vs. plain silence.
🐌 Naive
Every seat independently flips a coin each tick — no coordination, no idea who else is talking.
Tick 0Informed 0/0Collisions 0
🧠 Smart
A graph-coloring rotation computed once from the seating chart — no two seats that share a listener ever talk on the same tick.
Tick 0Informed 0/0Collisions 0
Theory corner. This table has – seats and – whisper-links (a sparse graph — far fewer than the n·(n-1)/2 links a full mesh would need). The Smart rotation needs – colors to guarantee zero collisions.
Paper's sparse bound Õ((mn)^0.6)
–
time steps, order-of-magnitude
Prior general bound O(n^1.33)
–
time steps, order-of-magnitude
These are asymptotic, hidden-constant/polylog-factor bounds meant for large n — at tabletop sizes (n≤10) they're illustrative context, not a prediction of the exact tick counts you'll see race above. The live race is the real experiment; the numbers above are the paper's math for why the gap widens as tables (and networks) get bigger and sparser.