Communication complexity of fault-tolerant information diffusion

This paper considers problems of fault-tolerant information diffusion in a network with cost function. We show that the problem of determining the minimum cost necessary to perform fault-tolerant gossiping among a given set of participants is NP-hard and given approximate (with respect to the cost) algorithms. We also analyze the communication time of fault-tolerant gossiping algorithms. Finally, we give an optimal cost fault tolerant broadcasting algorithm and apply our results to the atomic commitment problem