Project topics and materials
Get Complete Project Material File(s) Now! »
Overview of Gossip Protocols
Classic Results
In this section we brie y review what is known about the rumor spreading pro-cesses. We start by clarifying in which processes refer to rumor spreading and stating three basic examples { push, pull, and push-pull protocols. Then, we dis-cuss the di erence between synchronous and asynchronous rumor spreading. We provide some classic results for di erent network topologies and for both models of synchronization, that better illustrates the di erence between them. Finally we consider the case of the rumor spreading in the fully connected network. We discuss the ideas of the proofs for the known estimates of the runtime explaining why the precise analysis of the rumor spreading time in the complete graph can is a challenging problem.
Definition of Rumor Spreading
Despite the intuitiveness, it is hard to de ne precisely which processes refer to the rumor spreading. We have not found any general de nition in the literature, so let us propose the following scheme. The rumor spreading is a special class of dissemination processes in the network. By the dissemination process we mean the following.
De nition (dissemination process). Let G denote a simple and connected graph with n vertices. Initially one vertex of G knows the rumor that has to be conveyed to every other vertex of G. Each node i is controlled by some algorithm Ai which determines how node i spreads the rumor to its neighbors in G. The spread time or runtime is the time elapsed before every node knows the rumor.
The set of algorithms Ai determines the concrete process. Very often Ai are the same, so that the behavior of any node determines the whole process. Intuitively, if the behavior of Ai is similar to the \real world gossiping », then they determine a rumor spreading process. More formally, the rumor spreading is a dissemination process which satis es certain requirements.
De nition (Rumor spreading process). We call dissemination process gossip-based (or rumor spreading) if the following properties are satis ed.
(i) All interactions between nodes are pairwise. Each node can participate in only limited number of simultaneous communications.
(ii) There is some form of randomness in the choice of communication partners.
(iii) The information exchanged during these interactions is of bounded size.
(iv) The interaction frequency is low compared to typical message latencies so that the protocol cost is negligible.
The nature of the requirements is the following. First, (i) forbids any node to instantly broadcast the rumor to all its neighbors. Thus, communications re-mind the phone calls, hence we name them so.1 Second, (ii) requires the rumor spreading to be nondeterministic. Due to this condition the reasonable gossip protocols are simpler and better scalable than their deterministic competitors. In addition randomized gossip processes are robust, i.e., they work well even if reli-able communication is not assumed or there are some node failures in the network (see [FPRU90]). By (iii) and (iv), the duration of each communication is negligible, i.e., no over ow is possible (see discussion in the Section 3).
In this work we are interested by the runtime analysis for the di erent rumor spreading protocols. By the runtime or rumor spreading time we mean the time elapsed since the rumor appeared in the network until all nodes know of the rumor (see De nition II.13 for the synchronous model). The rumor spreading time is a random variable, so we are mostly interesting in the following characteristics.
De nition (Guaranteed and average rumor spreading times). Guaranteed spread-ing time is the smallest deterministic number t such that for any choice of initially informed vertex, the whole graph will be informed with high probability after the time t. Worst average spreading time is the smallest deterministic number t such that for every choice of initially informed vertex, the expected time until the whole graph is informed is at most t.
1 In most of the existing works, while the number of outgoing calls performed by a single node is limited, it is supposed that any node can reply all incoming requests. We discuss this assumption in Chapter IV, Section 3.
Remark.
(i) By high probability we understand the probability at least 1 o(1).
(ii) If it does not creates the ambiguity especially for the homogeneous rumor spreading studied so far, we will omit the word \worst » and say simply av-erage or expected spreading time.
It is worth to mention that the de nition above is suitable for both synchronous and asynchronous models. The main di erence between them is the following.
Synchronous model: Suppose that all nodes share a clock which rings at the discrete time steps. When the clock rings, a new round begins and nodes commu-nicate. All communications during the same round are considered simultaneous. Nevertheless, simultaneous communications are independent, i.e., if x calls y and y calls z in the same round but only x knows the rumor, then z will remain un-informed at the end round. If we assume that the time gap between rounds is 1, then the rumor spreading time is simply the number of rounds passed before all nodes are informed.
Asynchronous model: Each node decides to make a communication indepen-dently from the others according to its inner clock typically represented by a Poisson random variable of rate 1 [ACMW14] (see Section 1.3 of this chapter). Such model is also known as Richardson’s model [Ric73] after the rst who solved the problem proposed by Eden [Ede61] about the asynchronous rumor spreading on the square lattice.
Independent Random Phone-Call Model
Examples of Rumor Spreading Processes
In both synchronous and asynchronous models, the most classic gossip processes refer to the independent random phone-call model [DGH+87], [BEPS14], [PPS15], where each node chooses neighbors to call uniformly at random and independently2 from other nodes. Within each call the rumor spreads in a natural way, i.e., if the call is established between informed and uninformed node, then one of them for-wards the rumor to another. If both nodes are of the same status, then nothing happens. To distinguish two di erent mechanisms of informing we say that out-going call of an informed node is push call. Otherwise it is a pull call. Restricting the rumor spreading protocol to push-only or pull-only call mechanisms, we obtain push and pull protocol correspondingly. If both call mechanisms are allowed, we say that the rumor spreading follows the push-pull protocol.
De nition. Push protocol is the rumor spreading process in which only informed nodes can make calls. Basic push protocol is the synchronous push protocol in which each informed node makes exactly one call per round according the inde-pendent random phone-call model.
De nition. Pull protocol is the independent call gossip process in which only uninformed nodes can make calls. Basic pull protocol is the synchronous pull protocol in which each uninformed node makes exactly one call per round according the independent random phone-call model.
De nition. Push-pull protocol is the independent call gossip process in which each round every node is allowed to make calls. Basic push-pull protocol is the synchronous push-pull protocol in which each node makes exactly one call per round according the independent random phone-call model.
The basic versions of push, pull, and push-pull protocols are the simplest mod-els of rumor spreading processes. However, the application of basic protocols is often challenging and leads to certain generalizations.
Transmission failures: Usually the communications are not reliable. This en-vironment can be modeled by supposing that each call can be lost with respect to some independent Bernoulli random variable. Doerr et al.[DHL13] analyzed the push protocol where each call can be lost with the same probability 1 p. In Chapter IV, Section 2.1, we also discuss the pull and push-pull protocols.
Multiple calls: Di erent nodes may have di erent connection capacities and might participate in di erent number of communications per round. Panagiotou et al. [PPS15] proposed the gossip process where each node can call a random number of peers per round with respect to some distribution shared by all nodes. They considered two versions of this process. In the rst one, these random numbers are sampled in the beginning and stay constant for each node. In the second one, the number of communications re-samples each round for each node. We discuss the second version in Chapter IV, Section 2.2.
Stoppage problem for push calls: In the basic push and push-pull protocols, informed nodes make calls eternally regardless if everybody knows the rumor or not. One of the possible solution is the median counter algorithm [KSSV00] { a variance of the push-pull protocol in which informed nodes terminates the ru-mor spreading since they are principally called by informed nodes rather than by uninformed ones.
Multiple incoming pull calls: For the basic pull and push-pull protocols we suppose that if informed node receives several pull requests in one round, then it has enough time to forward the rumor to all its interlocutors. Sometimes it is worth to limit the number of transactions per node in one round by constant. Daum et al. [DKM15] proposed the process where all extra pull request are dropped that is a natural idea for the phone-call model. In Chapter IV, Section 3, we re ned their analysis for the complete graph.
Asynchronous Rumor Spreading
Now we discuss the relations between spreading time for the synchronous and asynchronous rumor speading. The fundamental question is what are the minimum and maximum spreading times in arbitrary n-vertex graph G? The answer was given by Acan, Collevecchio, Mehrabian, and Wormald [ACMW14]. Considering the basic push-pull protocol, they obtained the tight bounds, up to the constant factor cited in this section as Theorems II.1|II.4.
For the guaranteed and average spreading time we will follow the notation of Acan et al. Thus, gsta(G) and gsts(G) mean the guaranteed spreading time of graph G in asynchronous and synchronous modes, respectively. Correspondingly, wasta(G) and wasts(G) { the worst average spreading time of graph G in asyn-chronous and synchronous modes. Their rst result compares the guaranteed and the worst average spreading time in the asynchronous setting.
Table of contents :
I Introduction
1 What Is Rumor Spreading
2 Motivation
3 State of the Art
4 Our Contribution
5 Plan of the Work
II Overview of Gossip Protocols
1 Classic Results
1.1 Denition of Rumor Spreading
1.2 Independent Random Phone-Call Model
1.3 Asynchronous Rumor Spreading
1.4 Path, Square Lattice, Star, Necklace
1.5 Complete Graph. Overview of the Proofs
2 Precise Statements of Our Results
2.1 Tight Bounds via a Target-Failure Calculus
2.2 Uniform Treatment of Many Rumor Spreading Processes
2.3 Precise Statement of the Technical Results
2.4 Applying the Above Technical Results
2.5 Limitations of the Phase Method
III Main Analysis Technique
1 Homogeneous Rumor Spreading Processes
2 Exponential Growth Regime
2.1 Upper Bound
2.2 Lower Bound
3 Exponential Shrinking Regime
3.1 Upper Bound
3.2 Lower Bound
4 Double Exponential Shrinking Regime
4.1 Upper Bound
4.2 Lower Bound
IV Applications of our Method
1 Classic Protocols
1.1 Push Protocol
1.2 Pull Protocol
1.3 Push-Pull Protocol
2 Robustness, Multiple Calls, and Dynamic Graphs
2.1 Transmission Failures
2.2 Multiple Calls
2.3 Dynamic Graphs
3 Limited Incoming Calls Capacity
3.1 Single Incoming Call Push-Pull Protocol
3.2 Single Incoming Call Pull-Only Protocol
3.3 Push-Pull Protocol with Transition Time
V Non-Homogeneous Rumor Spreading
1 Two-State Multi-Parametric Process
2 Multi-State Rumor Spreading. Independent Stop Process
2.1 One Push Call per Node
2.2 Pull Protocol with C 1 Push Calls:
2.3 Random Stop Decision
3 Multiparametric exponential growth
VI Summary
1 Outlook
2 Open Problems
A Probabilistic notions
B First Order Bounds
C Coupon Collector and Ball into Bin
