Lower Bounds on Information Dissemination in Dynamic Networks
详细信息 查看全文
- 作者：Bernhard Haeupler (17)
Fabian Kuhn (18) - 刊名：Lecture Notes in Computer Science
- 出版年：2012
- 出版时间：2012
- 年：2012
- 卷：7611
- 期：1
- 页码：181-194
- 全文大小：315KB
- 参考文献：1. Anta, A.F., Milani, A., Mosteiro, M.A., Zaks, S.: Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol.?6343, pp. 374-88. Springer, Heidelberg (2010) CrossRef
2. Avin, C., Koucky, M., Lotker, Z.: How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). In: Aceto, L., Damg?rd, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.?5125, pp. 121-32. Springer, Heidelberg (2008) CrossRef
3. Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. In: Proc. 28th ACM Symp. on Principles of Distributed Computing (PODC), pp. 260-69 (2009)
4. Clementi, A., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time in edge-markovian dynamic graphs. In: Proc. of 27th ACM Symp. on Principles of Distributed Computing (PODC), pp. 213-22 (2008)
5. Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. Journal of Computer and System Sciences?75(4), 213-30 (2009) CrossRef
6. Clementi, A., Pasquale, F., Monti, A., Silvestri, R.: Information spreading in stationary markovian evolving graphs. In: Proc. of IEEE Symp. on Parallel & Distributed Processing, IPDPS (2009)
7. Clementi, A., Silvestri, R., Trevisan, L.: Information spreading in dynamic graphs. In: Proc. 31st Symp. on Principles of Distributed Computing, PODC (2012)
8. Cornejo, A., Gilbert, S., Newport, C.: Aggregation in dynamic networks. In: Proc. 31st Symp. on Principles of Distributed Computing, PODC (2012)
9. Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z.: Information spreading in dynamic networks. CoRR, abs/1112.0384 (2011)
10. Haeupler, B.: Analyzing network coding gossip made easy. In: Proc. 43nd Symp. on Theory of Computing (STOC), pp. 293-02 (2011)
11. Haeupler, B., Karger, D.: Faster information dissemination in dynamic networks via network coding. In: Proc. 30th Symp. on Principles of Distributed Computing (PODC), pp. 381-90 (2011)
12. Haeupler, B., Médard, M.: One packet suffices - highly efficient packetized network coding with finite memory. In: 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1151-155 (2011)
13. Jackson, B., Jordán, T.: Independence free graphs and vertex connectivity augmentation. Journal of Combinatorial Theory, Series B?94(1), 31-7 (2005) CrossRef
14. Kuhn, F., Lenzen, C., Locher, T., Oshman, R.: Optimal gradient clock synchronization in dynamic networks. In: Proc. of 29th ACM Symp. on Principles of Distributed Computing (PODC), pp. 430-39 (2010)
15. Kuhn, F., Lynch, N., Newport, C., Oshman, R., Richa, A.: Broadcasting in unreliable radio networks. In: Proc. of 29th ACM Symp. on Principles of Distributed Computing (PODC), pp. 336-45 (2010)
16. Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proc. 42nd Symp. on Theory of Computing (STOC), pp. 557-70 (2010)
17. Kuhn, F., Moses, Y., Oshman, R.: Coordinated consensus in dynamic networks. In: Proc. 30th Symp. on Principles of Distributed Computing (PODC), pp. 1-0 (2011)
18. Kuhn, F., Oshman, R.: Dynamic networks: Models and algorithms. SIGACT News?42(1), 82-6 (2011) CrossRef
19. O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proc. of Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104-10 (2005) - 作者单位：Bernhard Haeupler (17)
Fabian Kuhn (18)
17. Computer Science and Artificial Intelligence Lab, MIT, USA
18. Dept. of Computer Science, University of Freiburg, Germany
文摘
We study lower bounds on information dissemination in adversarial dynamic networks. Initially, k pieces of information (henceforth called tokens) are distributed among n nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied. If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all k tokens to all the nodes in O(nk) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Ω(n--em class="a-plus-plus">nk/logn) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways. If nodes are allowed to forward b?≤-em class="a-plus-plus">k tokens instead of only one token in every round, a straight-forward extension of the O(nk) algorithm disseminates all k tokens in time O(nk/b). We show that for any randomized token-forwarding algorithm, Ω(n--em class="a-plus-plus">nk/(b 2lognloglogn)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is c-vertex connected in every round, we show a lower bound of Ω(nk/(clog3/2 n)), which almost matches the currently best O(nk/c) upper bound. Further, if the network is T-interval connected, a notion that captures connection stability over time, we prove that Ω(n--em class="a-plus-plus">nk/(T 2logn)) rounds are needed. The best known upper bound in this case manages to solve the problem in O(n--em class="a-plus-plus">nk/T) rounds. Finally, we show that even if each node only needs to obtain a δ-fraction of all the tokens for some δ?∈?[0,1], Ω(nkδ 3/logn) are still required.