Communication Complexity of Gossiping by Packets |
| |
Affiliation: | 1. Institute for Information Law, University of Amsterdam, Amsterdam, Netherlands;2. SnT – Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg City, Luxembourg |
| |
Abstract: | This paper considers the problem of gossiping with packets of limited size in a network with a cost function. We show that the problem of determining the minimum cost necessary to perform gossiping among a given set of participants with packets of limited size is NP-hard. We also give an approximate (with respect to the cost) gossiping algorithm. The ratio between the cost of an optimal algorithm and the approximate one is less than 1 + 2(k− 1)/n, wherenis the number of nodes participating in the gossiping process andk≤n− 1 is the upper bound on the number of individual blocks of information that a packet can carry. We also analyze the communication time and communication complexity, i.e., the product of the communication cost and time, of gossiping algorithms. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|