, on suppose qu'un noeud ne fait plus d'appels une fois qu'il a obtenu l'information souhaitée, il y aurait alors uniquement n ? 1 transmission de l'information. Cette hypothèse est néanmoins peu réaliste. En effet, un noeud ne sachant pas à quel moment la nouvelle information apparaît sur le réseau
, il est possible d'avoir uniquement n ? 1 transmissions mais avec un temps de diffusion ?(n log n) Il suffit que seul le noeud à l'origine de l'information s'occupe des transmissions et ne la transmette que si un de ses voisins la lui demande pour la première fois ; mais en imposant que tous les noeuds doivent avoir reçu l'information en O(log n) étapes alors
, Order optimal information spreading using algebraic gossip A random graph model for power law graphs Tight bounds for quasirandom rumor spreading [AG06] I. Abraham et C. Gavoille : Object location using path separators, Applying static network protocols to dynamic networks Dans les actes de : 30th annual ACM SIGACT-SIGOPS symposium on Principles of Distributed Computing (PODC) 25th annual ACM symposium on Principles of distributed computing (PODC)AHK94] R. Ahlswede, H. S. Haroutunian et L. H. Khachatrian : Messy Broadcasting in Networks. 1994. [AKL08] C. Avin, M. Koucký et Z. Lotker : How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). Dans les actes de : 35th International Colloquium on Automata, Languages and Programming (ICALP), pp.358-370, 1987.
, Upfal : Towards robust and efficient computation in dynamic peer-to-peer networks The probabilistic method Efficient randomised broadcasting in random regular networks with applications in peer-topeer systems, les actes de : 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) Parsimonious flooding in dynamic graphs. Distributed Computing ACM symposium on Principles of Distributed Computing (PODC), pp.551-56931, 2000.
, Communication complexity of quasirandom rumor spreading, les actes de : 18th Annual European Symposium (ESA), pp.134-145, 2010.
, Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks, Second International Conference on Ad- Hoc, Mobile, and Wireless Networks (ADHOC-NOW), volume 2865 de Lecture Notes in Computer Science, pp.259-270, 2003.
DOI : 10.1007/978-3-540-39611-6_23
, Sub-linear Universal Spatial Gossip Protocols, 16th International Colloquium Structural Information and Communication Complexity (SIROCCO), pp.44-56, 2010.
DOI : 10.1137/0147013
, The worst case behavior of randomized gossip, les actes de : 9th annual conference on Theory and Applications of Models of Computation (TAMC), pp.330-345, 2012.
, Efficient Routing in Networks with Long Range Contacts, 15th International Conference on Distributed Computing (DISC), volume 2180 de Lecture Notes in Computer Science, pp.270-284, 2001.
DOI : 10.1007/3-540-45414-4_19
, Randomized gossip algorithms, IEEE Transactions on Information Theory, vol.52, issue.6, pp.2508-2530, 2006.
DOI : 10.1109/TIT.2006.874516
, Message Multicasting in Heterogeneous Networks, SIAM Journal on Computing, vol.30, issue.2, pp.347-358, 2000.
DOI : 10.1137/S0097539798347906
, On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization, Journal of Computer and System Sciences, vol.45, issue.1, pp.104-126, 1992.
DOI : 10.1016/0022-0000(92)90042-H
, Partial information spreading with application to distributed maximum coverage, Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '10, pp.161-170, 2010.
DOI : 10.1145/1835698.1835739
, The Diameter of Sparse Random Graphs, Advances in Applied Mathematics, vol.26, issue.4, pp.257-279, 2001.
DOI : 10.1006/aama.2001.0720
, Connected Components in Random Graphs with Given Expected Degree Sequences, Annals of Combinatorics, vol.6, issue.2, pp.125-145, 2002.
DOI : 10.1007/PL00012580
, The average distance in a random graph with given expected degrees Complex Graphs and Networks The volume of the giant component of a random graph with given expected degrees, CL07] N. B. Chang et M. Liu : Controlled flooding search in a large network, pp.91-113395, 2003.
, Information survival threshold in sensor and P2P networks Almost tight bounds for rumour spreading with conductance Rumour spreading and graph conductance Flooding time of edge-Markovian evolving graphs Epidemic algorithms for reliable content-based publish-subscribe : An evaluation Broadcasting in dynamic radio networks, les actes de : 42nd ACM Symposium on Theory of Computing (STOC) Dans les actes de : 21rst Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) les actes de : 24th International Conference on Distributed Computing Systems (ICDCS) : Information spreading in stationary Markovian evolving graphs. IEEE Transactions on Parallel and Distributed Systems MANETS : High mobility can make up for low transmission power. Dans les actes de : 36th International Colloquium on Automata, Languages and Programming (ICALP)CR06] A. Czumaj et W. Rytter : Broadcasting algorithms in radio networks with unknown topologyCS11] A. E. F. Clementi et R. Silvestri : Parsimonious flooding in geometric random-walks. Dans les actes de : 25th international conference on Distributed computing (DISC), pp.436-449, 2004.
, Quasirandom rumor spreading, Journal of Experimental Algorithmics, vol.16, 2011.
DOI : 10.1145/1963190.2025379
URL : http://arxiv.org/abs/1012.5351
, Quasirandom rumor spreading, les actes de : 19th annual ACM-SIAM symposium on Discrete algorithms (SODA), pp.773-781, 2008.
DOI : 10.1145/1963190.2025379
URL : http://arxiv.org/abs/1012.5351
, Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness, les actes de : 36th International Colloquium on Automata, Languages and Programming (ICALP), pp.366-377, 2009.
DOI : 10.1007/978-3-642-02927-1_31
, Epidemic algorithms for replicated database maintenance, ACM Operating Systems Review, SIGOPS, issue.1, pp.228-260, 1988.
, Thresholds for virus spread on networks, The Annals of Applied Probability, vol.18, issue.2, pp.359-378, 2008.
DOI : 10.1214/07-AAP470
, Schabanel : Could any graph be turned into a small-world ? Theoretical Computer Science, pp.96-103, 2006.
, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE Transactions on Information Theory, vol.52, issue.6, pp.2486-2507, 2006.
DOI : 10.1109/TIT.2006.874532
, Sublogarithmic approximation for telephone multicast, les actes de : 14th Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pp.76-85, 2003.
DOI : 10.1016/j.jcss.2005.12.002
URL : http://doi.org/10.1016/j.jcss.2005.12.002
, A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem, SIAM Journal on Computing, vol.35, issue.3, pp.672-689, 2005.
DOI : 10.1137/S0097539704440740
, On the communication complexity of randomized broadcasting in random-like graphs, les actes de : 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp.148-157, 2006.
, Rényi : On random graphs, Publicationes Mathematicae Debrecen, vol.6, pp.290-291, 1959.
, The power of memory in randomized broadcasting, les actes de : 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.218-227, 2008.
, On the runtime and robustness of randomized broadcasting, Theoretical Computer Science, vol.410, issue.36, pp.3414-3427, 2009.
DOI : 10.1016/j.tcs.2008.04.017
, Boosting gossip for live streaming Eclecticism shrinks even small worlds. Distributed Computing Fountoulakis et A. Huber : Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading Methods and problems of communication in usual networks Lotker : A lower bound for network navigability, 10th IEEE International Conference on Peer-to-Peer Computing (P2P)FPRU90] U. Feige, D. Peleg, P. Raghavan et E. Upfal : Randomized broadcast in networks. Random Structures & Algorithms Panagiotou et T. Sauerwald : Ultra-fast rumor spreading in social networks. Dans les actes de : 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). [Fra05] P. Fraigniaud : Greedy routing in tree-decomposed graphs. Dans les actes de : 13th Annual European Symposium on Algorithms (ESA), volume 3669 de Lecture Notes in Computer Science, pp.410-431, 1964.
, Random graphs Computers and Intractability : Efficient and adaptive epidemic-style protocols for reliable and scalable multicast, 28th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 9 de Leibniz International Proceedings in Informatics (LIPIcs), pp.57-681141, 1959.
, Analyzing network coding gossip made easy Dynamic graph models Harutyunyan : Improved messy broadcasting in hypercubes and complete bipartite graphs, les actes de : 43rd ACM Symposium on Theory of Computing (STOC) Liestman : A survey of gossiping and broadcasting in communication networks. Networks, pp.477-486, 1988.
, Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping) Jarry et Z. Lotker : Connectivity in evolving graph with geometric properties Müller : The minimum broadcast time problem for several processor networks, Messy broadcasting. Parallel Processing Letters joint workshop on Foundations of mobile computing (DIALM-POMC) Luczak et A. Rucinski : Random Graphs. Wiley- Interscience Series in Discrete Mathematics and Optimization. 2000. [JM95] K. Jansen et H, pp.149-159, 1995.
, The complexity of broadcasting in planar and decomposable graphs, les actes de : 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 1995.
, Gossiping in Minimal Time, SIAM Journal on Computing, vol.21, issue.1, pp.111-139, 1992.
DOI : 10.1137/0221010
, Gossip-based computation of aggregate information, 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.482-491, 2003.
DOI : 10.1109/SFCS.2003.1238221
, Protocols and impossibility results for gossip-based communication mechanisms, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp.471-480, 2002.
DOI : 10.1109/SFCS.2002.1181971
, Spatial gossip and resource location protocols, Journal of the ACM, vol.51, issue.6, pp.943-967, 2004.
DOI : 10.1145/1039488.1039491
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.8038
, The small-world phenomenon : an algorithm perspective, Thirty Second Annual ACM Symposium on Theory of Computing (STOC), pp.163-170, 2000.
, Distributed computation in dynamic networks, Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, pp.513-522, 2010.
DOI : 10.1145/1806689.1806760
, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, vol.27, issue.3, pp.702-712, 1998.
DOI : 10.1137/S0097539794279109
, Approximation Algorithms for Minimum-Time Broadcast, SIAM Journal on Discrete Mathematics, vol.8, issue.3, pp.401-427, 1995.
DOI : 10.1137/S0895480193245923
, Vocking : Randomized rumor spreading, les actes de : 41st Annual Symposium on Foundations of Computer Science (FOCS), pp.565-574, 2000.
, A Self-repairing Peer-to- Peer System Resilient to Dynamic Adversarial Churn, de Lecture Notes in Computer Science, 2005.
, A Self-repairing Peer-to- Peer System Resilient to Dynamic Adversarial Churn, de Lecture Notes in Computer Science, 2005.
, Search and replication in unstructured peer-to-peer networks, les actes de : 16th international conference on Supercomputing (ICS), pp.84-95, 2002.
, Route driven gossip: probabilistic reliable multicast in ad hoc networks, IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), pp.2229-2239, 2003.
DOI : 10.1109/INFCOM.2003.1209243
, Geographic routing in social networks, National Academy of Sciences of the United States of America, vol.102, issue.33, pp.11623-11628, 2005.
, The diameter of random massive graphs, 12th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA), pp.912-921, 2001.
, Symphony : Distributed hashing in a small world, les actes de : USENIX Symposium on Internet Technologies and Systems (USITS), 2003.
, Minimum broadcast time is np-complete for 3- regular planar graphs and deadline 2, Information Processing Letters, vol.46, issue.6, pp.281-287, 1993.
, The small world problem, Psychology Today, vol.1, issue.1, pp.60-67, 1967.
, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.179-188, 2004.
DOI : 10.1145/1011767.1011794
, Viceroy, Proceedings of the twenty-first annual symposium on Principles of distributed computing , PODC '02, pp.183-192, 2002.
DOI : 10.1145/571825.571857
, III : Bicriteria network design problems, Journal of Algorithms, vol.28, issue.1, pp.142-171, 1998.
, Analyzing and characterizing small-world graphs, les actes de : 16th annual ACM-SIAM symposium on Discrete algorithms (SODA), pp.311-320, 2005.
, An optimal greedy heuristic to color interval graphs, Information Processing Letters, vol.37, issue.1, pp.21-25, 1991.
, Pittel : On spreading a rumor, SIAM Journal on Applied Mathematics, vol.47, issue.1, pp.213-223, 1987.
, Accessing nearby copies of replicated objects in a distributed environment, Theory of Computing Systems, pp.241-280, 1999.
, Rapid rumor ramification : approximating the minimum broadcast time, 35th Annual Symposium on Foundations of Computer Science (FOCS), pp.202-213, 1994.
, On mixing and edge expansion properties in randomized broadcasting, 18th International Symposium on Algorithms and Computation (ISAAC), pp.196-207, 2007.
, Information Dissemination in Trees, SIAM Journal on Computing, vol.10, issue.4, pp.692-701, 1981.
DOI : 10.1137/0210052
, The Impact of Mobility on Gossip Algorithms, IEEE Transactions on Information Theory, vol.58, issue.3, pp.1731-1742, 2012.
DOI : 10.1109/TIT.2011.2177753
, Slivkins : Distance estimation and object location via rings of neighbors, Distributed Computing, vol.19, pp.313-333, 2007.
, Efficient content location using interest-based locality in peer-to-peer systems, IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), pp.2166-2176, 2003.
DOI : 10.1109/INFCOM.2003.1209237
, Rumor Spreading and Vertex Expansion on Regular Graphs, les actes de : 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.462-475, 2011.
DOI : 10.1137/1.9781611973082.37
, Strogatz : Collective dynamics of 'small-world' networks, Nature, vol.393, issue.6684, pp.440-442, 1998.
DOI : 10.1038/30918
, Using the small-world model to improve Freenet performance, Computer Networks, vol.46, issue.4, pp.555-574, 2004.
DOI : 10.1016/j.comnet.2004.05.004