Optimal Fast Solutions to the Gossip Problem

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.