Information spreading in dynamic graphs

详细信息    查看全文

• 作者：Andrea Clementi (1)
  Riccardo Silvestri (2)
  Luca Trevisan (3)
  
  1. Dipartimento di Ingegneria dell鈥橧mpresa ; Universit脿 Tor Vergata di Roma ; Roma ; Italy
  2. Dipartimento di Informatica ; Sapienza Universit脿 di Roma ; Roma ; Italy
  3. Department of Computer Science ; Stanford University ; Stanford ; CA ; USA
  
• 关键词：Dynamic graphs ; Flooding protocols ; Markov chains ; Mobility models
• 刊名：Distributed Computing
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：28
• 期：1
• 页码：55-73
• 全文大小：314 KB
• 参考文献：1. Aldous, D., Fill, J.A.: Reversible Markov Chains and Random Walks on Graphs, Chap. 14 (1999). lass="a-plus-plus">http://www.stat.berkeley.edu/aldous/RWG/book.html
  2. Avin, C., Koucky, M., Lotker, Z.: How to explore a fast-changing world. In: Proceedings of 35th ICALP鈥?8, LNCS, vol. 5125, pp. 121鈥?32 (2008)
  3. Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocation. SIAM J. Comput. lass="a-plus-plus">29(1), 180鈥?00 (1999) lass="external" href="http://dx.doi.org/10.1137/S0097539795288490" target="_blank" title="It opens in new window">CrossRef
  4. Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. Distrib. Comput. lass="a-plus-plus">24(1), 31鈥?4 (2011) lass="external" href="http://dx.doi.org/10.1007/s00446-011-0133-9" target="_blank" title="It opens in new window">CrossRef
  5. Becchetti, L., Clementi, A.E.F., Pasquale, F., Resta, G., Santi, P., Silvestri, R.: Information spreading in opportunistic networks is fast. lass="a-plus-plus">arXiv:1107.5241v1 (2011)
  6. Bettstetter, C., Resta, G., Santi, P.: The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Trans. Mob. Comput. lass="a-plus-plus">2, 257鈥?69 (2003) lass="external" href="http://dx.doi.org/10.1109/TMC.2003.1233531" target="_blank" title="It opens in new window">CrossRef
  7. Camp, T., Boleng, J., Davies, V.: A survey of mobility models for ad hoc network research. Wirel. Commun. Mob. Comput. lass="a-plus-plus">2(5), 483鈥?02 (2002) lass="external" href="http://dx.doi.org/10.1002/wcm.72" target="_blank" title="It opens in new window">CrossRef
  8. Camp, T., Navidi, W., Bauer, N.: Improving the accuracy of random waypoint simulations through steady-state initialization. In: Proceedings of 15th Interantional Conference on Modelling and Simulation, pp. 319鈥?26 (2004)
  9. Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumor spreading in social networks. Theor. Comput. Sci. lass="a-plus-plus">412(24), 2602鈥?610 (2011) lass="external" href="http://dx.doi.org/10.1016/j.tcs.2010.11.001" target="_blank" title="It opens in new window">CrossRef
  10. Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. J. Comput. Syst. Sci. lass="a-plus-plus">75(4), 213鈥?30 (2009) lass="external" href="http://dx.doi.org/10.1016/j.jcss.2008.10.004" target="_blank" title="It opens in new window">CrossRef
  11. Clementi, A., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-Markovian evolving graphs. SIAM J. Discrete Math. lass="a-plus-plus">24(4), 1694鈥?712 (2010) lass="external" href="http://dx.doi.org/10.1137/090756053" target="_blank" title="It opens in new window">CrossRef
  12. Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Information spreading in stationary markovian evolving graphs. IEEE Trans. Parallel Distrib. Syst. lass="a-plus-plus">22(9), 1425鈥?432 (2011) lass="external" href="http://dx.doi.org/10.1109/TPDS.2011.33" target="_blank" title="It opens in new window">CrossRef
  13. Clementi, A., Pasquale, F., Silvestri, R.: Opportunistic manets: high mobility can make up for low transmission power. IEEE/ACM Trans. Netw. lass="a-plus-plus">21(2), 610鈥?20 (2013) lass="external" href="http://dx.doi.org/10.1109/TNET.2012.2204407" target="_blank" title="It opens in new window">CrossRef
  14. Clementi, A., Monti, A., Silvestri, R.: Flooding over Manhattan. Distrib. Comput. lass="a-plus-plus">26(1), 25鈥?8 (2013) lass="external" href="http://dx.doi.org/10.1007/s00446-012-0182-8" target="_blank" title="It opens in new window">CrossRef
  15. Clementi, A., Monti, A., Silvestri, R.: Modelling mobility: a discrete revolution. Ad Hoc Netw. lass="a-plus-plus">9(6), 998鈥?014 (2011) lass="external" href="http://dx.doi.org/10.1016/j.adhoc.2010.09.002" target="_blank" title="It opens in new window">CrossRef
  16. Dimitriou, T., Nikoletseas, S., Spirakis, P.: The infection time of graphs. Discrete Appl. Math. lass="a-plus-plus">154(8), 2577鈥?589 (2006) lass="external" href="http://dx.doi.org/10.1016/j.dam.2006.04.026" target="_blank" title="It opens in new window">CrossRef
  17. Easley, D., Kleinberg, J.: Networks, Crowds, and Markets. Cambridge University Press, Cambridge (2010)
  18. Ghosh, B., Leighton, F.T., Maggs, B.M., Muthukrishnan, S., Plaxton, C.G., Rajaraman, R., Richa, A.W., Tarjan, R.E., Zuckerman, D.I.: Tight analyses of two local load balancing algorithms. SIAM J. Comput. lass="a-plus-plus">29(1), 29鈥?4 (1999) lass="external" href="http://dx.doi.org/10.1137/S0097539795292208" target="_blank" title="It opens in new window">CrossRef
  19. Grindrod, P., Higham, D.J.: Evolving graphs: dynamical models, inverse problems and propagation. Proc. R. Soc. A lass="a-plus-plus">466(2115), 753鈥?70 (2010) lass="external" href="http://dx.doi.org/10.1098/rspa.2009.0456" target="_blank" title="It opens in new window">CrossRef
  20. Jacquet, P., Mans, B., Rodolakis, G.: Information propagation speed in mobile and delay tolerant networks. IEEE Trans. Inf. Theory lass="a-plus-plus">56, 5001鈥?015 (2010) lass="external" href="http://dx.doi.org/10.1109/TIT.2010.2059830" target="_blank" title="It opens in new window">CrossRef
  21. Karagiannis, T., Le Boudec, J.-Y., Vojnovic, M.: Power law and exponential decay of inter contact times between mobile devices. In: Proceedings of 13th ACM MOBICOM, pp. 183鈥?94 (2007)
  22. Kesten, H., Sidoravicius, V.: The spread of a rumor or infection in a moving population. Ann. Probab. lass="a-plus-plus">33(6), 2402鈥?462 (2005) lass="external" href="http://dx.doi.org/10.1214/009117905000000413" target="_blank" title="It opens in new window">CrossRef
  23. Khun, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of 42nd ACM STOC, pp. 513鈥?22 (2010)
  24. Khun, F., Oshman, R.: Dynamic networks: models and algorithms. ACM SIGACT News lass="a-plus-plus">42(1), 82鈥?6 (2011) lass="external" href="http://dx.doi.org/10.1145/1959045.1959064" target="_blank" title="It opens in new window">CrossRef
  25. Lam, H., Liu, Z., Mitzenmacher, M., Sun, X., Wang, Y.: Information dissemination via random walks in d-dimensional space. In: Proceedings of 23rd ACM-SIAM SODA, pp. 1612鈥?622 (2012)
  26. Le Boudec, J.-Y., Vojnovic, M.: The random trip model: stability, stationary regime, and perfect simulation. IEEE/ACM Trans. Netw. lass="a-plus-plus">14(6), 1153鈥?166 (2006) lass="external" href="http://dx.doi.org/10.1109/TNET.2006.886311" target="_blank" title="It opens in new window">CrossRef
  27. Le Boudec, J.-Y.: Understanding the simulation of mobility models with palm calculus. Perform. Eval. lass="a-plus-plus">64(2), 126鈥?47 (2007) lass="external" href="http://dx.doi.org/10.1016/j.peva.2006.03.001" target="_blank" title="It opens in new window">CrossRef
  28. Peres, Y., Sinclair, A., Sousi, P., Stauffer, A.: Mobile geometric graphs: detection, coverage and percolation. In: Proceedings of 22nd ACM-SIAM SODA, pp. 412鈥?28 (2011)
  29. Pettarin, A., Pietracaprina, A., Pucci, G., Upfal, E.: Tight bounds on information dissemination in sparse mobile networks. In: Proceedings of 30th ACM PODC, pp. 355鈥?62 (2011)
  30. Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load-balancing schemes. In: Proceedings of 39th IEEE FOCS, pp. 694鈥?03 (1998)
  31. Spyropoulos, T., Jindal, A., Psounis, K.: An analytical study of fundamental mobility properties for encounter based protocols. Int. J. Auton. Adapt. Commun. Syst. lass="a-plus-plus">1(1), 4鈥?0 (2008) lass="external" href="http://dx.doi.org/10.1504/IJAACS.2008.019198" target="_blank" title="It opens in new window">CrossRef
  32. Vojnovic, M., Proutier, A.: Hop limited flooding over dynamic networks. In: Proceedings of 30th IEEE INFOCOM, pp. 685鈥?93 (2011)
  33. Whitbeck, J., Conan, V., de Amorim, M.D.: Performance of opportunistic epidemic routing on edge-Markovian dynamic graphs. IEEE Trans. Commun. lass="a-plus-plus">59(5), 1259鈥?263 (2011) lass="external" href="http://dx.doi.org/10.1109/TCOMM.2011.020811.090163" target="_blank" title="It opens in new window">CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Computer Communication Networks
  Computer Hardware
  Computer Systems Organization and Communication Networks
  Software Engineering, Programming and Operating Systems
  Theory of Computation
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0452

文摘

We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary ergodic Markovian dynamic graph processes, that is, processes in which the topology of the graph at time \(t\) depends only on its topology at time \(t-1\) and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and ergodic. Under general conditions, we bound the flooding time in terms of the mixing time of the dynamic graph process. We recover, as special cases of our result, bounds on the flooding time for the random trip model and the random path one; previous analysis techniques provided bounds only in restricted settings for such models. Our result also provides the first bound for the random waypoint model whose analysis had been an important open question. The bound is tight for the most realistic ranges of the network parameters.