Large computer networks are an essential part of modern technology, and quite often information needs to be broadcast to all the computers in the network. If all computers work perfectly all the time, this is simple. Suppose, however, that some of the computers fail occasionally. What is the fastest way to ensure that with high probability all working computers get the information? In this paper, we analyze three algorithms to do so. All algorithms terminate in logarithmic time, assuming computers fail with probability @math independently of each other. We prove that the third algorithm, which runs in time @math , is asymptotically optimal.
The topic of broadcasting information to all nodes of a network has been extensively studied for many different models. For a survey of the different models, see Pelc @cite_4 . Gasieniec and Pelc @cite_2 gave an algorithm working in @math (under slightly different assumptions then ours), Diks and Pelc @cite_6 improved this to @math (see also @cite_15 ). Results for some variation on the model can be found in @cite_8 @cite_9 @cite_1 @cite_12 @cite_16 . In all of these the analysis is up to a constant, whereas we determine the optimal running time up to @math . For examples of real world systems using such broadcasting algorithms, see @cite_7 @cite_11 . Frieze and Grimmett @cite_3 studied the running time of the naive algorithm when there are no faults ( @math ). Their result was further refined by Pittel @cite_5 . Our Theorem generalizes these results to all @math . Doerr, Huber and Levavi @cite_13 analyzed the naive algorithm in the case of faulty links, instead of nodes, getting the same running time as in our Thoerem .
@cite_4 @cite_7 @cite_8 @cite_9 @cite_1 @cite_6 @cite_3 @cite_2 @cite_5 @cite_15 @cite_16 @cite_13 @cite_12 @cite_11
2063105299 1857436971 1980048622 2061408752 2173651310 2059014957 2056496732 1984977694 2102879646 1508237135 2052326735
Broadcasting and gossiping are fundamental tasks in network communication. In broadcasting, or one-to-all communication, information originally held in one node of the network (called the source) must be transmitted to all other nodes. In gossiping, or all-to-all communication, every node holds a message which has to be transmitted to all other nodes. As communication networks grow in size, they become increasingly vulnerable to component failures. Thus, capabilities for fault-tolerant broadcasting and gossiping gain importance. The present paper is a survey of the fast-growing area of research investigating these capabilities. We focus on two most important efficiency measures of broadcasting and gossiping algorithms: running time and number of elementary transmissions required by the communication process. We emphasize the unifying thread in most results from the research in fault-tolerant communication: the trade-offs between efficiency of communication schemes and their fault-tolerance. © 1996 John Wiley & Sons, Inc. Management of forthcoming exascale clusters requires frequent collection of run-time information about the nodes and the running applications. This paper presents a new paradigm for providing online information to the management system of scalable clusters, consisting of a large number of nodes and one or more masters that manage these nodes. We describe the details of resilient gossip algorithms for sharing local information within subsets of nodes and for sending global information to a master, which holds information on all the nodes. The presented algorithms are decentralized, scalable and resilient, working well even when some nodes fail, without needing any recovery protocol. The paper gives formal expressions for approximating the average ages of the local information at each node and the information collected by the master. It then shows that these results closely match the results of simulations and measurements on a real cluster. The paper also investigates the resilience of the algorithms and the impact on the average age when nodes or masters fail. The main outcome of this paper is that partitioning of large clusters can improve the quality of information available to the management system without increasing the number of messages per node. Copyright © 2015 John Wiley & Sons, Ltd. A variant of the well-known gossip problem is studied. Each of n members of a communication network has a piece of information that should be made known to everybody else. This is to be done by placing a sequence of two-party phone calls along the lines of the network. During each call, the two participants exchange all information they currently have, in a unit of time. It is assumed that calls fail independently with fixed probability @math and that no information is exchanged during a failed call. For communication networks of bounded degree, efficient schemes of calls are shown that assure complete communication with probability converging to 1 as n grows. Both the number of calls and the time they use are of minimal order. Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability0 We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted to all other fault-free processors. We assume that the fraction f n of faulty processors is bounded by a constant γ<1 . Transmissions are fault free. Faults are assumed to be of the crash type: faulty processors do not send or receive messages. We use the whispering model: pairs of processors communicating in one round must form a matching. A fault-free processor sending a message to another processor becomes aware of whether this processor is faulty or fault free and can adapt future transmissions accordingly. The main result of the paper is a broadcasting algorithm working in O( log n) rounds and using O(n) messages of logarithmic size, in the worst case. This is an improvement of the result from [17] where O ((log n) 2 ) rounds were used. Our method also gives the first algorithm for adaptive distributed fault diagnosis in O( log n) rounds. 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. 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). 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. We revisit the classic problem of spreading a piece of information in a group of @math n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903---912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of @math O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization). 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 (1+ -o(1)) factors. We limit ourselves to the network in which the vertices form a clique. 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 probability p@?(0,1], after (1+@e)(1log"2(1+p)log"2n+1plnn) rounds where @e>0 is fixed, the quasirandom protocol has informed all n nodes in the network with probability at least 1-n^-^p^@e^ ^4^0. Note that this is slightly faster than the intuitively natural 1 p factor increase over the run-time of approximately log"2n+lnn 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 consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an “off-line” algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault tolerance of broadcasting schemes in trees. We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn2+n2logn), where n is the size of the tree. We also give an algorithm to find a “universally fault-tolerant” broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, for all k simultaneously.