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 give approximate (with respect to the cost) fault-tolerant gossiping algorithms. We also analyze the communication time and communication complexity of fault-tolerant gossiping algorithms. Finally, we give an optimal cost fault tolerant broadcasting algorithm and apply our results to the atomic commitment problem.