Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we aim at bridging this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the rumor-spreading problem and the majority-consensus problem, two fundamental tasks in distributed computing, and initiate their study under communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each synchronous round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability 1 2-e, for some small Ae >0. Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy rumor-spreading and the noisy majority-consensus problems efficiently. Our protocols run in O(log n e2) rounds and use O(n log n e2) messages bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by the source. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.
Disseminating information to all the nodes of a network is one of the most fundamental communication primitives. In particular, the broadcast problem, where a single piece of information initially residing at some source node is to be disseminated, and variants of it have received a lot of attention in the literature, see, e.g., @cite_7 @cite_47 @cite_39 @cite_46 @cite_33 @cite_57 @cite_56 @cite_58 @cite_49 @cite_9 @cite_15 . Much of this research was devoted to bounding measures such as the number of rounds, and the total number of messages. Fault tolerant broadcast algorithms have also been studied extensively, especially in complete networks and in synchronous environments, where the focus has been on weak types of failures such as (probabilistic) message failures and initial node crashes. Essentially, it has been shown that there exist broadcast protocols that can overcome such faults with a relatively little penalty @cite_39 @cite_19 @cite_29 @cite_51 @cite_56 @cite_54 @cite_9 @cite_58 .
@cite_47 @cite_33 @cite_7 @cite_15 @cite_9 @cite_29 @cite_54 @cite_39 @cite_57 @cite_56 @cite_19 @cite_49 @cite_46 @cite_58 @cite_51
2068322213 2038562061 2068749247 2157004711 2953373073 2952550120 1865724022 2952030388 2056496732 2775875217 179639306 2026433959 2071202952 1970542229
In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the 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 the LOCAL model, this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the GOSSIP model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm, in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance φ and graph size n, culminating in a bound of O(φ-1 log n). In this paper, we show that a fairly simple modification of the protocol gives an algorithm that solves the information dissemination problem in at most O(D + polylog (n)) rounds in a network of diameter D, with no dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of D, which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires T rounds in the LOCAL model can be simulated in O(T + polylog(n)) rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent. Whru a dilt lhSC is replicated at, many sites2 maintaining mutual consistrnry among t,he sites iu the fac:e of updat,es is a signitirant problem. This paper descrikrs several randomized algorit,hms for dist,rihut.ing updates and driving t,he replicas toward consist,c>nc,y. The algorit Inns are very simple and require few guarant,ees from the underlying conllllunicat.ioll system, yc+ they rnsutc t.hat. the off( c t, of (‘very update is evcnt,uwlly rf+irt-ted in a11 rq1ica.s. The cost, and parformancc of t,hr algorithms arc tuned I>? c oosing appropriat,c dist,rilMions in t,hc randoinizat,ioii step. TIN> idgoritlmls ilr(’ c*los *ly analogoIls t,o epidemics, and t,he epidcWliolog)litc , ilitlh iii Illld rsti4lldill tlicir bc*liavior. One of tlW i$,oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv(brs of thr Xerox C’orporat c Iiitcrnc4, solviiig long-standing prol>lf lns of high traffic and tlatirl>ilsr inconsistcllcp. We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange messages during a round only with the player that u called, and with all the players that @math received calls from, in that round. In every round, a (possibly empty) set of rumors to be distributed among all players is generated, and each of the rumors is initially placed in a subset of the players. Karp et. al Karp2000 showed that no rumor-spreading algorithm that spreads a rumor to all players with constant probability can be both time-optimal, taking O(lg n) rounds, and message-optimal, using O(n) messages per rumor. For address-oblivious algorithms, in particular, they showed that Ω(n lg lg n) messages per rumor are required, and they described an algorithm that matches this bound and takes O(lg n) rounds. We investigate the number of communication bits required for rumor spreading. On the lower-bound side, we establish that any address-oblivious algorithm taking O(lg n) rounds requires Ω(n (b+ lg lg n)) communication bits to distribute a rumor of size b bits. On the upper-bound side, we propose an address-oblivious algorithm that takes O(lg n) rounds and uses O(n(b+ lg lg n lg b)) bits. These results show that, unlike the case for the message complexity, optimality in terms of both the running time and the bit communication complexity is attainable, except for very small rumor sizes b 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. Randomized rumor spreading is a classical protocol to disseminate information across a network. At SODA 2008, a quasirandom version of this protocol was proposed and competitive bounds for its run-time were proven. This prompts the question: to what extent does the quasirandom protocol inherit the second principal advantage of randomized rumor spreading, namely robustness against transmission failures? In this paper, we present a result precise up to @math factors. We limit ourselves to the network in which every two vertices are connected by a direct link. Run-times accurate to their leading constants are unknown for all other non-trivial networks. We show that if each transmission reaches its destination with a probability of @math , after @math rounds the quasirandom protocol has informed all @math nodes in the network with probability at least @math . Note that this is faster than the intuitively natural @math factor increase over the run-time of approximately @math for the non-corrupted case. We also provide a corresponding lower bound for the classical model. This demonstrates that the quasirandom model is at least as robust as the fully random model despite the greatly reduced degree of independent randomness. We study gossip algorithms for the rumor spreading problem which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple and robust solutions to the rumor spreading problem. Recently, non-uniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-, STOC'12] gave an O(log^3 n) algorithm to solve the 1-local broadcast problem in which each node wants to exchange rumors locally with its 1-neighborhood. By repeatedly applying this protocol one can solve the global rumor spreading quickly for all networks with small diameter, independently of the conductance. This and all prior gossip algorithms for the rumor spreading problem have been inherently randomized in their design and analysis. This resulted in a parallel research direction trying to reduce and determine the amount of randomness needed for efficient rumor spreading. This has been done via lower bounds for restricted models and by designing gossip algorithms with a reduced need for randomness. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors. In this paper we improves over this state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem in 2(k+log n)log n rounds. Besides being the first efficient deterministic solution to the rumor spreading problem this algorithm is interesting in many aspects: It is simpler, more natural, more robust and faster than its randomized pendant and guarantees success with certainty instead of with high probability. Its analysis is furthermore simple, self-contained and fundamentally different from prior works. We propose a new protocol for the fundamental problem of disseminating a piece of information to all members of a group of n players. It builds upon the classical randomized rumor spreading protocol and several extensions. The main achievements are the following: Our protocol spreads a rumor from one node to all other nodes in the asymptotically optimal time of (1 + o(1)) log2 n. The whole process can be implemented in a way such that only O(nf(n)) calls are made, where f(n) = ω(1) can be arbitrary. In spite of these quantities being close to the theoretical optima, the protocol remains relatively robust against failures; for random node failures, our algorithm again comes arbitrarily close to the theoretical optima. The protocol can be extended to also deal with adversarial node failures. The price for that is only a constant factor increase in the run-time, where the constant factor depends on the fraction of failing nodes the protocol is supposed to cope with. It can easily be implemented such that only O(n) calls to properly working nodes are made. In contrast to the push-pull protocol by [FOCS 2000], our algorithm only uses push operations, i.e., only informed nodes take active actions in the network. On the other hand, we discard address-obliviousness. To the best of our knowledge, this is the first randomized push algorithm that achieves an asymptotically optimal running time. We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and strengthens previous results. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that it converges with high probability in the information-theoretically optimal time. Most stopping times are of the form O(k + T) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining". Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. While RLNC gossip works in this wide variety of networks its analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases. We consider broadcasting from a fault-free source to all nodes of a completely connected n-node network in the presence of k faulty nodes. Every node can communicate with at most one other node in a unit of time and during this period every pair of communicating nodes can exchange information packets. Faulty nodes cannot send information. Broadcasting is adaptive, i.e., a node schedules its next communication on the basis of information currently available to it. Assuming that the fraction of faulty nodes is bounded by a constant smaller than 1, we construct a broadcasting algorithm working in worst-case time O(log2 n). We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion α, we show that this protocol spreads a rumor from a single node to all other nodes in [EQUATION] rounds with high probability. Further, we construct graphs for which Ω(α−1 log2 n) rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion. In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good "Quality of Delivery," i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal. Gossip algorithms spread information in distributed networks by nodes repeatedly forwarding information to a few random contacts. By their very nature, gossip algorithms tend to be distributed and fault tolerant. If done right, they can also be fast and message-efficient. A common model for gossip communication is the random phone call model, in which in each synchronous round each node can PUSH or PULL information to or from a random other node. For example, [FOCS 2000] gave algorithms in this model that spread a message to all nodes in Θ(log n) rounds while sending only O(log log n) messages per node on average. They also showed that at least Θ(log n) rounds are necessary in this model and that algorithms achieving this round-complexity need to send ω(1) messages per node on average. Recently, Avin and Elsasser [DISC 2013], studied the random phone call model with the natural and commonly used assumption of direct addressing. Direct addressing allows nodes to directly contact nodes whose ID (e.g., IP address) was learned before. They show that in this setting, one can "break the log n barrier" and achieve a gossip algorithm running in O(√log n) rounds, albeit while using O(√log n) messages per node. In this paper we study the same model and give a simple gossip algorithm which spreads a message in only O(log log n) rounds. We furthermore prove a matching Ω(log log n) lower bound which shows that this running time is best possible. In particular we show that any gossip algorithm takes with high probability at least 0.99 log log n rounds to terminate. Lastly, our algorithm can be tweaked to send only O(1) messages per node on average with only O(log n) bits per message. Our algorithm therefore simultaneously achieves the optimal round-, message-, and bit-complexity for this setting. As all prior gossip algorithms, our algorithm is also robust against failures. In particular, if in the beginning an oblivious adversary fails any F nodes our algorithm still, with high probability, informs all but o(F) surviving nodes. In this paper, we study the following randomized broadcasting protocol. At some time t an information r is placed at one of the nodes of a graph. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of r to it. We begin by developing tight lower and upper bounds on the runtime of the algorithm described above. First, it is shown that on ?-regular graphs this algorithm requires at least log2?1?n+log(???1)?n?o(logn)?1.69log2n rounds to inform all n nodes. Together with a result of Pittel B. Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, 47 (1) (1987) 213?223 this bound implies that the algorithm has the best performance on complete graphs among all regular graphs. For general graphs, we prove a slightly weaker lower bound of log2?1?n+log4n?o(logn)?1.5log2n, where ? denotes the maximum degree of G. We also prove two general upper bounds, (1+o(1))nlnn and O(n??), respectively, where ? denotes the minimum degree.The second part of this paper is devoted to the analysis of fault-tolerance. We show that if the informed nodes are allowed to fail in some step with probability 1?p, then the broadcasting time increases by at most a factor 6 p. As a by-product, we determine the performance of agent based broadcasting in certain graphs and obtain bounds for the runtime of randomized broadcasting on Cartesian products of graphs.