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.


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