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 determini ng the minimum cost necessary to perform fault-tolerant gossiping amon g a given set of participants is NP-hard and give approximate (with re spect to the cost) fault-tolerant gossiping algorithms. We also analyz e the communication time and communication complexity of fault-toleran t gossiping algorithms. Finally, we give an optimal cost fault-toleran t broadcasting algorithm and apply our results to the atomic commitmen t problem. (C) 1998-Elsevier Science B.V. All rights reserved.