Communication complexity of fault-tolerant information diffusion
Luisa Gargano, Adele Anna Rescigno · 2002
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.>