Gossiping by processors prone to omission failures

We consider the gossip problem in a synchronous message-passing system. Participating processors are prone to omission failures, that is, a faulty processor may fail to send or receive a message. The gossip problem in the fault-tolerant setting is defined as follows: every correct processor must learn the initial value of any other processor, unless the other one is faulty; in the latter case either the initial value or the information about the fault must be learned. We develop two efficient algorithms that solve the gossip problem in time O (log n), where n is the number of processors in the system. The first one is an explicit algorithm (i.e., constructed in polynomial time) sending O (n log n + f²) messages, and the second one reduces the message complexity to O (n + f²), where f is the upper bound on the number of faulty processors.