Optimal Fast Solutions to the Gossip Problem

Giulio Salerni1
1Piazza A. Zamorani 4, I-00157 Rome, Italy

Abstract

We present a new proof that the optimal fast solutions to the gossip problem, for an even number of participants \( n > 2^{\lceil \log_2{n} \rceil} – 2^{\lfloor \lceil \log_2{n} \rceil /2\rfloor} \), require exactly \( \frac{n}{2}\lceil \log_2{n} \rceil \) calls.

Keywords: Gossip problem, Fast solution, Optimal solution. AMS subject classification: 94A15.