Lower Bounds on Information Dissemination in Dynamic Networks

详细信息    查看全文

• 作者：Bernhard Haeupler (1) haeupler@mit.edu
  Fabian Kuhn (2) kuhn@cs.uni-freiburg.de
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7611
• 期：1
• 页码：166-180
• 全文大小：315.5 KB
• 参考文献：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–388. Springer, Heidelberg (2010)
  2. Avin, C., Kouck媒, 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–132. Springer, Heidelberg (2008)
  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–269 (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–222 (2008)
  5. Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. Journal of Computer and System Sciences 75(4), 213–230 (2009)
  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–302 (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–390 (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–1155 (2011)
  13. Jackson, B., Jord谩n, T.: Independence free graphs and vertex connectivity augmentation. Journal of Combinatorial Theory, Series B 94(1), 31–77 (2005)
  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–439 (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–345 (2010)
  16. Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proc. 42nd Symp. on Theory of Computing (STOC), pp. 557–570 (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–10 (2011)
  18. Kuhn, F., Oshman, R.: Dynamic networks: Models and algorithms. SIGACT News 42(1), 82–96 (2011)
  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–110 (2005)
• 作者单位：1. Computer Science and Artificial Intelligence Lab, MIT, USA2. Dept. of Computer Science, University of Freiburg, Germany
• ISSN：1611-3349

文摘

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.