Gossiping Without Duplicate Transmissions

摘要

N people have distinct bits of information, which they communicate via telephone calls in which they transmit everything they know. We require that no one ever hear the same piece of information twice. In the case 4 divides n, n > or = 8, we provide a construction that transmits all information using only 9n/4-6 calls. Previous construction used 1/2n log n calls. (Author)