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

Diks, Krzysztof; Pelc, Andrzej

SIAM J. Discrete Math. 5, No. 3, 338-344 (1992).

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

Keywords:

communication networks; gossip schemes; random faults; reliability; gossip problem; communication network; information