Communication complexity of fault-tolerant information diffusion
作者： Luisa Gargano , Adele A. Rescigno
DOI: 10.1016/S0304-3975(97)00109-6
关键词: Atomic commitment 、 Communication complexity 、 Set (abstract data type) 、 Mathematical optimization 、 Function (mathematics) 、 Mathematics 、 Fault tolerance 、 Diffusion (acoustics) 、 Optimal cost 、 Gossip 、 Algorithm
摘要: This paper considers problems of fault-tolerant information diffusion in a network with cost function. We show that the problem determining minimum necessary to perform gossiping among given set participants is NP-hard and give approximate (with respect cost) algorithms. also analyze communication time complexity Finally, we an optimal broadcasting algorithm apply our results atomic commitment problem.
elsevier.com
sci-hub.se 参考文章(43)
Combinatorial Network Theory : Kluwer Academic Publishers. ,(1996) , 10.1007/978-1-4757-2491-2
Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro, Communication Complexity of Gossiping by Packets scandinavian workshop on algorithm theory. pp. 234- 245 ,(1996) , 10.1007/3-540-61422-2_135
László Lovász, Combinatorial problems and exercises ,(1979)
John N. Tsitsiklis, Dimitri P. Bertsekas, Parallel and Distributed Computation: Numerical Methods ,(1989)
Danny Dolev, Cynthia Dwork, Larry Stockmeyer, On the minimal synchronism needed for distributed consensus Journal of the ACM. ,vol. 34, pp. 77- 97 ,(1987) , 10.1145/7531.7533
S. Even, B. Monien, On the number of rounds necessary to disseminate information Proceedings of the first annual ACM symposium on Parallel algorithms and architectures - SPAA '89. pp. 318- 327 ,(1989) , 10.1145/72935.72969
Magnus Broberg, Lars Lundberg, Håkan Grahn, Performance Optimization Using Extended Critical Path Analysis in Multithreaded Programs on Multiprocessors Journal of Parallel and Distributed Computing. ,vol. 61, pp. 115- 136 ,(2001) , 10.1006/JPDC.2000.1667
Adele A. Rescigno, On the communication complexity of polling Information Processing Letters. ,vol. 59, pp. 317- 323 ,(1996) , 10.1016/0020-0190(96)00127-5
Brenda Baker, Robert Shostak, Gossips and telephones Discrete Mathematics. ,vol. 2, pp. 191- 193 ,(1972) , 10.1016/0012-365X(72)90001-5
Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro, Fast Gossiping by Short Messages SIAM Journal on Computing. ,vol. 27, pp. 917- 941 ,(1998) , 10.1137/S0097539795283619