On the complexity of information spreading in dynamic networks
We study how to spread k tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O(n + k) rounds in any static network, and determining its complexity in dynamic networks is central to understandin...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/106636 http://hdl.handle.net/10220/25043 http://www.scopus.com/record/display.url?eid=2-s2.0-84876015544&origin=inward&txGid=C00E313D39DE2E098A6CDB1A0981DEA2.aqHV0EoE4xlIF3hgVWgA%3a2 |
| _version_ | 1826113074005803008 |
|---|---|
| author | Dutta, Chinmoy Pandurangan, Gopal Rajaraman, Rajmohan Sun, Zhifeng Viola, Emanuele |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Dutta, Chinmoy Pandurangan, Gopal Rajaraman, Rajmohan Sun, Zhifeng Viola, Emanuele |
| author_sort | Dutta, Chinmoy |
| collection | NTU |
| description | We study how to spread k tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O(n + k) rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits and capabilities of various dynamic network models. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them. We first consider the strongly adaptive adversary model where in each round, each node first chooses a token to broadcast to all its neighbors (without knowing who they are), and then an adversary chooses an arbitrary connected communication network for that round with the knowledge of the tokens chosen by each node. We show that Ω(nk/ log n + n) rounds are needed for any randomized (centralized or distributed) token-forwarding algorithm to disseminate the k tokens, thus resolving an open problem raised in [KLO10]. The bound applies to a wide class of initial token distributions, including those in which each token is held by exactly one node and well-mixed ones in which each node has each token independently with a constant probability. Our result for the strongly adaptive adversary model motivates us to study the weakly adaptive adversary model where in each round, the adversary is required to lay down the network first, and then each node sends a possibly distinct token to each of its neighbors. We propose a simple randomized distributed algorithm where in each round, along every edge (u, v), a token sampled uniformly at random from the symmetric difference of the sets of tokens held by node u and node v is exchanged. We prove that starting from any well-mixed distribution of tokens where each node has each token independently with a constant probability, this algorithm solves the k-gossip problem in O((n + k) log n log k) rounds with high probability over the initial token distribution and the randomness of the protocol. We then show how the above uniform sampling problem can be solved using Õ(log n) bits of communication, making the overall algorithm communication-efficient. We next present a centralized algorithm that solves the gossip problem for every initial distribution in O((n + k) log2 n) rounds in the offline setting where the entire sequence of communication networks is known to the algorithm in advance. Finally, we present an O(n min{k, √k log n})-round centralized offline algorithm in which each node can only broadcast a single token to all of its neighbors in each round. |
| first_indexed | 2024-10-01T03:17:14Z |
| format | Conference Paper |
| id | ntu-10356/106636 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:17:14Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/1066362023-02-28T19:17:13Z On the complexity of information spreading in dynamic networks Dutta, Chinmoy Pandurangan, Gopal Rajaraman, Rajmohan Sun, Zhifeng Viola, Emanuele School of Physical and Mathematical Sciences Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (24th : 2013) DRNTU::Science::Mathematics::Discrete mathematics::Algorithms We study how to spread k tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O(n + k) rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits and capabilities of various dynamic network models. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them. We first consider the strongly adaptive adversary model where in each round, each node first chooses a token to broadcast to all its neighbors (without knowing who they are), and then an adversary chooses an arbitrary connected communication network for that round with the knowledge of the tokens chosen by each node. We show that Ω(nk/ log n + n) rounds are needed for any randomized (centralized or distributed) token-forwarding algorithm to disseminate the k tokens, thus resolving an open problem raised in [KLO10]. The bound applies to a wide class of initial token distributions, including those in which each token is held by exactly one node and well-mixed ones in which each node has each token independently with a constant probability. Our result for the strongly adaptive adversary model motivates us to study the weakly adaptive adversary model where in each round, the adversary is required to lay down the network first, and then each node sends a possibly distinct token to each of its neighbors. We propose a simple randomized distributed algorithm where in each round, along every edge (u, v), a token sampled uniformly at random from the symmetric difference of the sets of tokens held by node u and node v is exchanged. We prove that starting from any well-mixed distribution of tokens where each node has each token independently with a constant probability, this algorithm solves the k-gossip problem in O((n + k) log n log k) rounds with high probability over the initial token distribution and the randomness of the protocol. We then show how the above uniform sampling problem can be solved using Õ(log n) bits of communication, making the overall algorithm communication-efficient. We next present a centralized algorithm that solves the gossip problem for every initial distribution in O((n + k) log2 n) rounds in the offline setting where the entire sequence of communication networks is known to the algorithm in advance. Finally, we present an O(n min{k, √k log n})-round centralized offline algorithm in which each node can only broadcast a single token to all of its neighbors in each round. Published version 2015-02-12T08:43:56Z 2019-12-06T22:15:22Z 2015-02-12T08:43:56Z 2019-12-06T22:15:22Z 2013 2013 Conference Paper Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z., & Viola, E. (2013). On the complexity of information spreading in dynamic networks. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 717-736. https://hdl.handle.net/10356/106636 http://hdl.handle.net/10220/25043 http://www.scopus.com/record/display.url?eid=2-s2.0-84876015544&origin=inward&txGid=C00E313D39DE2E098A6CDB1A0981DEA2.aqHV0EoE4xlIF3hgVWgA%3a2 en © 2013 Society for Industrial and Applied Mathematics. This paper was published in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following URL: [http://www.scopus.com/record/display.url?eid=2-s2.0-84876015544&origin=inward&txGid=C00E313D39DE2E098A6CDB1A0981DEA2.aqHV0EoE4xlIF3hgVWgA%3a2]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. 28 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms Dutta, Chinmoy Pandurangan, Gopal Rajaraman, Rajmohan Sun, Zhifeng Viola, Emanuele On the complexity of information spreading in dynamic networks |
| title | On the complexity of information spreading in dynamic networks |
| title_full | On the complexity of information spreading in dynamic networks |
| title_fullStr | On the complexity of information spreading in dynamic networks |
| title_full_unstemmed | On the complexity of information spreading in dynamic networks |
| title_short | On the complexity of information spreading in dynamic networks |
| title_sort | on the complexity of information spreading in dynamic networks |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Algorithms |
| url | https://hdl.handle.net/10356/106636 http://hdl.handle.net/10220/25043 http://www.scopus.com/record/display.url?eid=2-s2.0-84876015544&origin=inward&txGid=C00E313D39DE2E098A6CDB1A0981DEA2.aqHV0EoE4xlIF3hgVWgA%3a2 |
| work_keys_str_mv | AT duttachinmoy onthecomplexityofinformationspreadingindynamicnetworks AT pandurangangopal onthecomplexityofinformationspreadingindynamicnetworks AT rajaramanrajmohan onthecomplexityofinformationspreadingindynamicnetworks AT sunzhifeng onthecomplexityofinformationspreadingindynamicnetworks AT violaemanuele onthecomplexityofinformationspreadingindynamicnetworks |