On the number of rounds necessary to disseminate information
Shimon Even, Burkhard Monien · 1989
Assume each processor in a network has some piece of information.We study how efficiently information can be spread in a communication network.Specifically, we investigate the number of rounds necessary to spread all the pieces of information to all processors.This problem is known as the "gossip" problem, and initially, the question was to determine the number of telephone calls necessary to achieve complete dissemination.In this paper we study the "telegraph comnmnication node", where in each round, each processor is active only via one of its links and the communication is one-way, i.e. each processor can either transmit or receive, but not both.For an even number of processors, we prove upper and lower bounds on the number of rounds needed for disseminating the information in this telegraph mode.The two bounds are related to Fibonacci numbers and differ by, at most, an additive constant of 1.Our lower bound technique uses elements from matrix theory, specifically matrix norms.These results show, for the first time, that in the two-way mode, information can be distributed faster than in the one-way mode.Similar techniques are applied to obtain upper and lower bounds on the number of rounds needed for gossip in other communication modes.We consider the (pR, qS)communication modes, where during each round each processor can receive information from at most p processors or can send information to at most q processors, but no processor can send and receive during the same round. ITechnion, Israel Institute