Parsimonious flooding in dynamic graphs

ABSTRACT

An edge-Markovian process with birth-rate p and death-rate q generates sequences of graphs (G₀,G₁,G₂,…) with the same node set [n] such that G_t is obtained from G_t−1 as follows: if e ∉ E(G_t−1) then e ∈ E(G_t) with probability p, and if e ∈ E(G_t−1) then e ∉ E(G_t) with probability q. Clementi et al. (PODC 2008) analyzed thoroughly information dissemination in such dynamic graphs, by establishing bounds on their flooding time--flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t∦ > t. In this paper, we establish tight bounds on the complexity of flooding for all possible birth rates and death rates, completing the previous results by Clementi et al. Moreover, we note that despite its many advantages in term of simplicity and robustness, flooding suffers from its high bandwidth consumption. Hence we also show that flooding in dynamic graphs can be implemented in a more parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time.

For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ∈ [n], the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that it is even constant whenever the ratio p/(p + q) exceeds log n/n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs.

REFERENCES

• 1: N. Alon, J. H Spencer. The Probabilistic Method. Wiley (2000).
• 2: Chen Avin , Michal Koucký , Zvi Lotker, How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs), Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_11]
• 3: B. Bollobás. Random Graphs. Cambridge University Press (2001).
• 4: F. Brauer, P. van den Driessche, and J. Wu (Eds). Mathematical Epidemiology. Lecture Notes in Mathematics, subseries in Mathematical Biosciences Subseries, Vol. 1945, 2008.
• 5: D. Chakrabarti, J. Leskovec, C. Faloutsos, S. Madden, C. Guestrin, and M. Faloutsos. Information survival threshold in sensor and P2P networks. In 26th IEEE International Conference on Computer Communications (INFOCOM), pages 1316--1324, 2007.
• 6: Nicholas B. Chang , Mingyan Liu, Controlled flooding search in a large network, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.436-449, April 2007 [doi>10.1109/TNET.2007.892880]
• 7: Fan Chung , Linyuan Lu, The diameter of sparse random graphs, Advances in Applied Mathematics, v.26 n.4, p.257-279, May 2001 [doi>10.1006/aama.2001.0720]
• 8: Andrea E.F. Clementi , Claudio Macci , Angelo Monti , Francesco Pasquale , Riccardo Silvestri, Flooding time in edge-Markovian dynamic graphs, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400781]
• 9: Andrea E. F. Clementi , Francesco Pasquale , Angelo Monti , Riccardo Silvestri, Communication in dynamic radio networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281131]
• 10: Andrea E. F. Clementi , Francesco Pasquale , Angelo Monti , Riccardo Silvestri, Information spreading in stationary Markovian evolving graphs, Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing, p.1-12, May 23-29, 2009 [doi>10.1109/IPDPS.2009.5160986]
• 11: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 12: M. Draief, A. Ganesh, and L. Massoulié. Thresholds for virus spread on networks. Ann. Appl. Probab. 18(2):359-378, 2008.
• 13: Uriel Feige , David Peleg , Prabhakar Raghavan , Eli Upfal, Randomized Broadcast in Networks, Proceedings of the International Symposium on Algorithms, p.128-137, August 16-18, 1990
• 14: Pierre Fraigniaud , Emmanuel Lazard, Methods and problems of communication in usual networks, Discrete Applied Mathematics, v.53 n.1-3, p.79-133, Sept. 14, 1994
• 15: A. Frieze and G. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Math. 10:57--77, 1985.
• 16: Gnutella RFC. http://rfc-gnutella.sourceforge.net/
• 17: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 18: Indranil Gupta , Anne-Marie Kermarrec , Ayalvadi J. Ganesh, Efficient Epidemic-Style Protocols for Reliable and Scalable Multicast, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems, p.180, October 13-16, 2002
• 19: S. Hedetniemi, S. Hedetniemi, and A. Liestman. A survey of gossiping and broadcasting in communication networks. Networks 18:319--349, 1986.
• 20: J. Hromković, R. Klasing, B. Monien, and R. Peine. Dissemination of information in interconnection networks (broadcasting and gossiping). Combinatorial Network Theory, pages 125--212. Kluwer Academic, D.-Z. Du and D. Hsu (eds), 1995.
• 21: S. Janson , T. Luczak, and A. Rucinski. Random Graphs. Wiley (2000).
• 22: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 23: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 24: David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
• 25: J. Luo, P. Eugster, and J.-P. Hubaux. Route driven gossip: probabilistic reliable multicast in ad hoc networks. In 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 2229--2239, 2003.
• 26: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 27: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 28: A. Sarwate and A. Dimakis. The Impact of Mobility on Gossip Algorithms. In 28th Conference on Computer Communications (INFOCOM), 2009.
• 29: K. Sripanidkulchai, B. Maggs, and H. Zhang. Efficient content location using interest-based locality in peer-to-peer systems. In 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 2166--2176, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Performance, Theory

Keywords:
broadcasting, epidemic protocol, evolving graphs, gossip protocol