Gossiping in a distributed network
Ann D. Bagchi, S. L. Hakimi, Edward F. Schmeichel · IEEE Transactions on Computers · 1993
Consider a network in which each unit initially knows only its own identity and the identity of its immediate neighbors. Suppose each unit has a message intended for all other units. The authors give a distributed algorithm to accomplish this in point-to-point networks which is optimal in the number of transmissions it requires. They also show that this algorithm accomplishes this efficiently for broadcast (radio) networks, although the problem of finding a solution with the least number of transmissions, in broadcast networks, is shown to be NP-hard.>