We perform a thorough study of various characteristics of the asynchronous push–pull protocol for spreading a rumor on Erdős–Renyi random graphs (G_ n,p ), for any (p>c (n) n ) with (c>1 ). In particular, we provide a simple strategy for analyzing the asynchronous push–pull protocol on arbitrary graph topologies and apply this strategy to (G_ n,p ). We prove tight bounds of logarithmic order for the total time that is needed until the information has spread to all nodes. Surprisingly, the time required by the asynchronous push–pull protocol is asymptotically almost unaffected by the average degree of the graph. Similarly tight bounds for Erdős–Renyi random graphs have previously only been obtained for the synchronous push protocol, where it has been observed that the total running time increases significantly for sparse random graphs. Finally, we quantify the robustness of the protocol with respect to transmission and node failures. Our analysis suggests that the asynchronous protocols are particularly robust with respect to these failures compared to their synchronous counterparts.
There are many theoretical studies that are concerned with the performance of the push-pull algorithm @cite_13 @cite_22 @cite_25 @cite_0 @cite_2 @cite_3 . For example, the performance of rumor spreading on general graph topologies was made explicit in @cite_13 @cite_22 @cite_2 , where the number of rounds necessary to spread a rumor was related to the conductance of the graph. In particular, the upper bound @math was shown, where @math is the conductance of the graph.
@cite_22 @cite_3 @cite_0 @cite_2 @cite_13 @cite_25
2167805066 2157004711 167256694 2103160469 2009356484 2621876985
We show that if a connected graph with n nodes has conductance p then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(log4 n p6) many steps, with high probability, using the PUSH-PULL strategy. An interesting feature of our approach is that it draws a connection between rumour spreading and the spectral sparsification procedure of Spielman and Teng [23]. Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for spl Theta (ln n) rounds needs to transmit the rumor spl Theta (n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send spl Omega (n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i.e. every algorithm that distributes a rumor in O(ln n) rounds needs spl omega (n) transmissions. We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent β > 2. Our main findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 3, then Ω(log n) rounds are necessary. We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the first result that establishes a gap between the synchronous and the asynchronous protocol. We study the connection between the rate at which a rumor spreads throughout a graph and the conductance of the graph—a standard measure of a graph’s expansion properties. We show that for any n-node graph with conductance , the classical PUSH-PULL algorithm distributes a rumor to all nodes of the graph in O( 1 logn) rounds with high probability (w.h.p.). This bound improves a recent result of Chierichetti, Lattanzi, and Panconesi [6], and it is tight in the sense that there exist graphs where ( 1 logn) rounds of the PUSH-PULL algorithm are required to distribute a rumor w.h.p. We also explore the PUSH and the PULL algorithms, and derive conditions that are both necessary and sucient for the above upper bound to hold for those algorithms as well. An We show that if a connected graph with @math nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(φ-1 • log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The O(••) notation hides a polylog φ-1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ-1 • log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds. Abstract It has been observed that information spreads extremely fast in social networks. We model social networks with the preferential attachment model of Barabasi and Albert (Science 1999) and information spreading with the random phone call model of (FOCS 2000). In a recent paper (STOC 2011), we prove the following two results. (i) The random phone call model delivers a message to all nodes of graphs in the preferential attachment model within Θ ( log n ) rounds with high probability. The best known bound so far was O ( log 2 n ) . (ii) If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one Θ ( log n log log n ) , which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding doublecontacts reduces the run-time to a smaller order of magnitude.