Efficient Gossiping by Packets in Networks with Random Faults

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 < 1$ and $q < 1$, respectively. Faults are permanent and of crash type: a faulty link does not transmit messages and a faulty node neither sends nor receives messages. In a unit of time, every node can send a packet of information to at most one neighbor and receive a packet from at most one neighbor. The size of each packet does not exceed $b(n)$, where n is the number of nodes. For every $\eta > 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.