Efficient Gossiping by Packets in Networks with Random Faults
Krzysztof Diks, Andrzej Pelc · SIAM Journal on Discrete Mathematics · 1996
Every node of a communication network has a constant size value which should be made known to all other nodes. Nodes and links fail independently with constant probabilities $p 0$ we present an algorithm to exchange values between all fault-free nodes of an n-node network in time $O(\frac{n}{b(n)}) + \log n$), with probability exceeding $1 - n^{ - \eta } $, for sufficiently large n. This order of magnitude of running time is optimal.