Almost safe gossiping in bounded degree networks.(English)Zbl 0768.05060

Summary: A variant of the well-known gossip problem is studied. Each of $$n$$ members of a communication network has a piece of information that should be made known to everybody else. This is to be done by placing a sequence of two-party phone calls along the lines of the network. During each call, the two participants exchange all information they currently have, in a unit of time. It is assumed that calls fail independently with fixed probability $$0<p<1$$ and that no information is exchanged during a failed call. For communication networks of bounded degree, efficient schemes of calls are shown that assure complete communication with probability converging to 1 as $$n$$ grows. Both the number of calls and the time they use are of minimal order.

MSC:

 05C38 Paths and cycles 94C15 Applications of graph theory to circuits and networks
Full Text: