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 synchronous push protocol there exist very accurate bounds of the spreading time @cite_5 @cite_18 @cite_26 . In @cite_26 it was shown that a rumor spreads in @math rounds w.h.p. on the complete graph. In @cite_5 it was shown that for @math with @math a rumor spreads w.h.p. in @math rounds. Furthermore, it was recently shown that the spreading time increases significantly when approaching the connectivity threshold more closely, namely that for @math with @math , @math , the spreading time is w.h.p. @math , where @math @cite_11 . This means in particular that the spreading time cannot be bounded by logarithmic time independent of the edge probability @math ; this is in contrast to the asynchronous push-pull algorithm, which is more robust with respect to variations in the average degree, cf. Theorem . On random regular graphs with degree @math , the spreading time has been shown to equal @math w.h.p. @cite_7 .
@cite_18 @cite_26 @cite_7 @cite_5 @cite_11
2059014957 1984977694 2137662992 2016123342 1992403724
We consider the problem of finding the shortest distance between all pairs of vertices in a complete digraph on n vertices, whose arc-lengths are non-negative random variables. We describe an algorithm which solves this problem in O(n(m+nlogn)) expected time, where m is the expected number of arcs with finite lenght. If m is small enough, this represents a small improvement over the bound in Bloniarz [3]. We consider also the case when the arc-lengths are random variables which are independently distributed with distribution function F, where F(0)=0 and F is differentiable at 0; for this case, we describe an algorithm which runs in O(n2logn) expected time. In our treatment of the shortest-path problem we consider the following problem in combinatorial probability theory. A town contains n people, one of whom knows a rumour. At the first stage he tells someone chosen randomly from the town; at each stage, each person who knows the rumour tells someone else, chosen randomly from the town and indeependently of all other choices. Let Sn be the number of stages before the whole town rnows the rumour. We show that Sn log2n → 1 + loge2 in probability as n → ∞, and estimate the probabilities of large deviations in Sn. Suppose that one of n people knows a rumor. At the first stage, he passes the rumor to someone chosen at random; at each stage, each person already informed (“knower”) communicates the rumor to a person chosen at random and independently of all other past and present choices. Denote by @math the random number of stages before everybody is informed. How large is @math typically? Frieze and Grimmet, who introduced this problem, proved that, in probability, @math . In this paper we show that, in fact, @math in probability. Our proof demonstrates that the number @math of persons informed after t stages obeys very closely, with high probability, a deterministic equation @math , @math . A case when each knower passes the rumor to several members at every stage is also discussed. Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well-studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d -regular graphs with n vertices. We show that with probability 1 - o(1) the push model broadcasts the message to all nodes within (1 + o(1))Cd lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo-random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 - o(1), where . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q that is, it fails to do so with probability 1-q. The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, with q=1 is very well understood. In particular, Frieze and Grimmett proved that with probability 1-o(1) the push protocol completes the broadcasting of the message within (1±e) (log_2 n + ln n) stages, where n is the number of nodes in the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. In this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. We show that if p≥ α(n)ln n n, where α(n) is any function that tends to infinity as n grows, then the push protocol with faulty transmissions broadcasts the message within (1±±&#949;)(log_ 1+q n + 1 q ln n) stages with probability 1-o(1). In other words, in almost every network of density d such that d ≥ α(n) ln n, the push protocol broadcasts a message as fast as in a fully connected network and the speed is only affected by the success probability q. This is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing. Our results are accompanied by experimental evaluation. We consider the popular and well-studied push model, which is used to spread information in a given network with n vertices. Initially, some vertex owns a rumour and passes it to one of its neighbours, which is chosen randomly. In each of the succeeding rounds, every vertex that knows the rumour informs a random neighbour. It has been shown on various network topologies that this algorithm succeeds in spreading the rumour within O(log n) rounds. However, many studies are quite coarse and involve huge constants that do not allow for a direct comparison between different network topologies. In this paper, we analyse the push model on several important families of graphs, and obtain tight runtime estimates. We first show that, for any almost-regular graph on n vertices with small spectral expansion, rumour spreading completes after log2n + log n+o(log n) rounds with high probability. This is the first result that exhibits a general graph class for which rumour spreading is essentially as fast as on complete graphs. Moreover, for the random graph G(n,p) with p=c log n n, where c > 1, we determine the runtime of rumour spreading to be log2n + γ (c)log n with high probability, where γ(c) = clog(c (c−1)). In particular, this shows that the assumption of almost regularity in our first result is necessary. Finally, for a hypercube on n=2d vertices, the runtime is with high probability at least (1+β) ⋅ (log2n + log n), where β > 0. This reveals that the push model on hypercubes is slower than on complete graphs, and thus shows that the assumption of small spectral expansion in our first result is also necessary. In addition, our results combined with the upper bound of O(log n) for the hypercube (see [11]) imply that the push model is faster on hypercubes than on a random graph G(n, clog n n), where c is sufficiently close to 1.