@math rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of @math is also known for this special case. Under the assumption of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses push&pull with pointer jumping to spread a rumor to all nodes in only @math rounds, w.h.p. This algorithm can also cope with @math node failures, in which case all but @math nodes become informed within @math rounds, w.h.p.
We propose and analyse a quasirandom analogue to the classical push model for disseminating information in networks ("randomized rumor spreading"). In the classical model, in each round each informed node chooses a neighbor at random and informs it. Results of Frieze and Grimmett (Discrete Appl. Math. 1985) show that this simple protocol succeeds in spreading a rumor from one node of a complete graph to all others within O(log n) rounds. For the network being a hypercube or a random graph G(n, p) with p ≥ (1 +e)(log n) n, also O(log n) rounds suffice (Feige, Peleg. Raghavan, and Upfal, Random Struct. Algorithms 1990). In the quasirandom model, we assume that each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above mentioned bounds still hold. In addition, we also show a O(log n) bound for sparsely connected random graphs G(n, p) with p = (log n + f(n)) n, where f(n) → ∞ and f(n) = O(log log n). Here, the classical model needs Θ(log2(n)) rounds. Hence the quasirandom model achieves similar or better broadcasting times with a greatly reduced use of random bits.  We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a channel to its ith neighbor (modulo degree) on that list, beginning from a randomly chosen starting position. Then, the channels can be used for bi-directional communication in that step. The goal is to spread a message efficiently to all nodes of the graph. We show three results. For random graphs (with sufficiently many edges) we present an address-oblivious algorithm with runtime O(log n) that uses at most O(n log log n) message transmissions. For hypercubes of dimension log n we present an address-oblivious algorithm with runtime O(log n) that uses at most O(n(log log n)2) message transmissions. For hypercubes we also show a lower bound of Ω(n log n log log n) on the total number of message transmissions required by any O(log n) time address-oblivious algorithm in the standard random phone call model. Together with a result of [8], our results imply that for random graphs and hypercubes the communication complexity of the quasirandom phone call model is significantly smaller than that of the standard phone call model. This seems to be surprising given the small amount of randomness used in our model. Randomized rumor spreading is an efficient protocol to distribute information in networks. Recently, a quasirandom version has been proposed and proven to work equally well on many graphs and better for sparse random graphs. In this work we show three main results for the quasirandom rumor spreading model. We exhibit a natural expansion property for networks which suffices to make quasirandom rumor spreading inform all nodes of the network in logarithmic time with high probability. This expansion property is satisfied, among others, by many expander graphs, random regular graphs, and Erdős-Renyi random graphs. For all network topologies, we show that if one of the push or pull model works well, so does the other. We also show that quasirandom rumor spreading is robust against transmission failures. If each message sent out gets lost with probability f , then the runtime increases only by a factor of @math . In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In this paper, we give an algorithm that solves the information dissemination problem in at most @math rounds in a network of diameter @math , withno dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of @math , which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires @math rounds in the LOCAL model can be simulated in @math rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent.