Fast information sharing in a complete network

The authors consider the problem of complete information dissemination among n autonomous processors in a fully connected distributed system. Initially, each processor possesses information not held by any other processor; it is required that all the processors obtain all the information in the shortest possible time. Messages are exchanged in discrete, synchronized rounds; message size is unlimited, but during a round, each processor may transmit messages to, or receive messages from, at most k other processors. The authors show that rounds are necessary for such an information exchange and that are sufficient, where . This settles in the affirmative a 10-year-old conjecture of Entringer and Slater; the present lower bound is new even for the case .