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.
For the asynchronous push-pull protocol there exists much less literature @cite_10 @cite_0 , mostly devoted to models for scale-free networks. In @cite_10 it was shown that on preferential attachment graphs a rumor needs a time of @math w.h.p. to spread to almost all nodes. On power-law Chung-Lu random graphs @cite_4 (for power-law exponent @math ) it was shown in @cite_0 that a rumor initially located within the giant component spreads w.h.p. even in constant time to almost all nodes. Related to the asynchronous push-pull protocol is first-passage percolation, which, on regular graphs, is an equivalent process. There, it has been shown that the running time on the hypercube and the complete graph is @math @cite_6 @cite_23 @cite_21 . In a recent study, the ratio of the spreading time of the synchronous and asynchronous push-pull protocol was bounded by @math from below and by @math from above @cite_12 . In particular, examples of graphs in which the asynchronous version spreads the rumor in logarithmic time and the synchronous version needs polynomial time were given.
@cite_4 @cite_21 @cite_6 @cite_0 @cite_23 @cite_10 @cite_12
2068902429 2031541804 2494932805 167256694 2005443809 2159732236 2885831468
Random graph theory is used to examine the "small-world phenomenon"– any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees, the average distance is almost surely of order log n logd where d is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1 k β for some fixed exponent β. For the case of β > 3, we prove that the average distance of the power law graphs is almost surely of order log n log d. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph... Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n n for two given points, that the maximum if one point is fixed and the other varies is 2 log n n, and that the maximum over all pairs of points is 3 log n n.Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths. 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. Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube Bn = 0, 1 with nearest neighbor edges. For oriented and unoriented percolation, p = e n and p = 1 n are the respective critical probabilities. For oriented first-passage percolation with i.i.d. edge-passage times having a density of 1 near the origin, the percolation time (time to reach the opposite corner of the cube) converges in probability to 1 as n → ∞. This resolves a conjecture of David Aldous. When the edge-passage distribution is standard exponential, the (smaller) percolation time for unoriented edges is at least 0.88. These results are applied to Richardson’s model on the (unoriented) n-cube. Richardson’s model, otherwise known as the contact process with no recoveries, models the spread of infection as a Poisson process on each edge connecting an infected node to an uninfected one. It is shown that the time to cover the entire n-cube is bounded between 1.41 and 14.05 in probability as n→∞. Research supported by the National Security Agency under Grant Number MDA904-89-H-2051. Research supported by a National Science Foundation postdoctoral fellowship and by a Mathematical Sciences Institute postdoctoral fellowship. AMS 1991 subject classifications. Primary 60K35; secondary 60C05. We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as defined by Barabasi and Albert) in time @math to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be Θ(logn loglogn).