Communication Complexity of Gossiping by Packets
作者： Luisa Gargano , Adele A. Rescigno , Ugo Vaccaro
关键词:
摘要: This paper considers the problem of gossiping with packets limited size in a network cost function. We show that determining minimum necessary to perform among given set participants is NP-hard. also give an approximate (with respect cost) algorithm. The ratio between optimal algorithm and one less than 1 + 2(k� 1)/n, wherenis number nodes participating process andk�n� upper bound on individual blocks information packet can carry. analyze communication time complexity, i.e., product time, algorithms.
elsevier.com
sci-hub.se 参考文章(24)
Jean-Claude Bermond, Takako Kodate, Stéphane Pérennes, Gossiping in Cayley Graphs by Packets Selected papers from the 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science. pp. 301- 315 ,(1995) , 10.1007/3-540-61576-8_91
Juraj Hromkovič, Ralf Klasing, Burkhard Monien, Regine Peine, Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping) Combinatorial Network Theory. pp. 125- 212 ,(1996) , 10.1007/978-1-4757-2491-2_5
André Hily, Dominique Sotteau, Communications in bus networks Proceedings of the first Canada-France conference on Parallel and distributed computing. pp. 197- 206 ,(1994) , 10.1007/3-540-58078-6_17
John N. Tsitsiklis, Dimitri P. Bertsekas, Parallel and Distributed Computation: Numerical Methods ,(1989)
R. Ravi, Rapid rumor ramification: approximating the minimum broadcast time foundations of computer science. pp. 202- 213 ,(1994) , 10.1109/SFCS.1994.365693
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
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
A. Bagchi, E. F. Schmeichel, S. L. Hakimi, Parallel Information Dissemination by Packets SIAM Journal on Computing. ,vol. 23, pp. 355- 372 ,(1994) , 10.1137/S0097539790192672
Luisa Gargano, Tighter time bounds on fault-tolerant broadcasting and gossiping Networks. ,vol. 22, pp. 469- 486 ,(1992) , 10.1002/NET.3230220505
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)