Information dissemination functions in communication networks
Anindo Bagchi · 1990
Consider a point-to-point network consisting of units and links which connect pairs of units. Suppose each of the knits possesses a unique message which has to be received by every other unit. This is called A related problem is that of census taking in which a particular unit has to receive the messages of every other unit. The units communicate by transmitting packets of a fixed size, so that only a bounded number of messages can be sent in a single transmission. We present heuristic algorithms for gossiping and census taking in general graphs. We describe algorithms for gossiping, using a minimum number of packets, in several prominent families of networks, e.g. trees, rings, etc. We also describe nearly optimal parallel algorithms for gossiping in such networks, when the packet sizes are bounded or unbounded. Next, we consider networks in which the units are only aware of their identities and the identities of their immediate neighbors. We present distributed algorithms for gossiping in such networks which are optimal in terms of the number of transmissions and the overall network utilization. We also describe a distributed algorithm for gossiping in the presence of faulty units which is asymptotically optimal. This algorithm is directly applicable to several other areas like leader election and distributed fault diagnosis. Finally, we study gossiping in broadcast (radio) networks. We discuss the complexity of the problem and present an efficient distributed algorithm for the same. In such networks we also study local gossiping. In this problem, each unit has to receive the messages of its immediate neighbors. Using extensions of well known results in graph theory, we design distributed algorithms for this problem.