Fast Gossip-based Rumor Spreading using Small Messages FABIEN DUFOULON, Lancaster University, UK WILLIAM K. MOSES JR., Durham University, UK GOPAL PANDURANGAN, University of Houston, USA We study gossip algorithms for the fundamental rumor spreading problem, where the goal is to disseminate a rumor from a given source node to all nodes in an arbitrary (and unknown) graph. Gossip algorithms allow each node to call only one neighbor per round
arXiv:2605.14376v1 [cs.DC] 14 May 2026
and are therefore highly message-efficient, with low per-node communication overhead per round. The state of the art present fast gossip algorithms, however they typically leverage large-sized messages. This undermines the light-weight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in 𝑛, the network size. Hence, a fundamental question is whether one can perform fast gossip using small messages. The main contribution of this paper is to answer the above question in the affirmative and present two gossip algorithms that achieve fast rumor spreading using messages of polylog 𝑛 size. Specifically, we show the following results: (1) We present a gossip algorithm for rumor spreading that runs in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds for every 𝑐 ⩾ 1, and Φ𝑐 is the weak conductance. Our algorithm’s run time not only improves over the Censor-Hillel-Shachnai bound [SODA 2011; SICOMP 2012], but more significantly, it uses messages of small (polylog 𝑛) size, unlike the prior work that used messages of large (at least linear in 𝑛) size. Our bound in terms of weak conductance is essentially optimal. (2) We also present a gossip algorithm for rumor spreading that depends on the network diameter (and is independent of the √ graph’s conductance), which runs in 𝑂˜ (𝐷 + 𝑛) rounds with high probability and uses small (polylog 𝑛 size) messages. Our √ bound is a significant improvement over the gossip algorithm of 𝑂˜ ( 𝑛𝐷 ) due to Ghaffari and Kuhn [DISC 2018], which also √ uses small-sized messages. We note that our algorithm (unlike that of Ghaffari and Kuhn) is optimal for when 𝐷 = Ω ( 𝑛). Furthermore, our gossip algorithm can be modified to output a minimum spanning tree (MST) in the same number of rounds, which is essentially round-optimal (even for non-gossip algorithms). Our gossip algorithms use graph sketches [Ahn, Guha, McGregor, SODA 2012] in a novel way to overcome communication bottlenecks and achieve small communication overhead with small message sizes. CCS Concepts: • Theory of computation → Distributed algorithms; • Mathematics of computing → Probabilistic algorithms; Discrete mathematics. Additional Key Words and Phrases: Gossip, Rumor Spreading, Congest, KT1, Broadcast ACM Reference Format: Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan. 2026. Fast Gossip-based Rumor Spreading using Small Messages. 1, 1 (May 2026), 28 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn
Authors’ Contact Information: Fabien Dufoulon, Lancaster University, Lancaster, UK, [email protected]; William K. Moses Jr., Durham University, Durham, UK, [email protected]; Gopal Pandurangan, University of Houston, Houston, USA, [email protected].
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. Manuscript submitted to ACM
Manuscript submitted to ACM
1
2 1
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan Introduction
Rumor spreading (also called broadcasting or information dissemination) is a fundamental network communication primitive that has been studied extensively for many decades under various models and assumptions [2–6, 12, 13, 16– 19, 21, 22, 30]. In the rumor spreading problem, we are given an arbitrary (connected) communication graph 𝐺 = (𝑉 , 𝐸) and a source node 𝑣 ∈ 𝑉 with a piece of information (a.k.a. “rumor") and the goal is to disseminate the rumor to all other nodes in the graph. As discussed later, it is easy to modify rumor spreading algorithms to compute node aggregate functions such as minimum, maximum, sum or average. (Throughout we use 𝑛 = |𝑉 | to denote the number of nodes in 𝐺, 𝑚 = |𝐸| for the number of edges in the network, and 𝐷 for the graph diameter.) We study gossip algorithms for rumor spreading. In gossip, each node is allowed to call only one neighbor per round. Hence, it is very message-efficient, with a small communication overhead per node per round. This is in contrast to other message-heavy broadcasting techniques such as flooding, where a node (with the rumor) forwards it to all neighbors (which can be as large as Θ(𝑛)) in a round. It is well-known that there are graphs where flooding can take Θ(𝑚) messages to spread the rumor to all nodes, but gossip takes only 𝑂˜ (𝑛) messages (𝑂˜ notation hides logarithmic in 𝑛 factors).1 A simple and well-studied gossip algorithm is uniform gossip where each node calls a random neighbor and exchanges the rumor (if any of them have it). More precisely, in uniform gossip, also called (uniform) push-pull gossip, in each round, each node 𝑣 with the rumor contacts a random neighbor and pushes the rumor to it, and each node 𝑢 that does not have the rumor, contacts a random neighbor and pulls the rumor from it (if the neighbor has it). A long line of research [7–10, 25] on uniform gossip culminated in showing that it takes 𝑂 ( Φ ) rounds (w.h.p.)2 where Φ is the log 𝑛
conductance (see Section 2.1) of the graph [6, 15]. In general, this bound is also tight as there are graphs where rumor spreading needs at least Ω( Φ ) rounds (e.g., a constant degree expander) [6, 15]. log 𝑛
Informally, conductance Φ ∈ [0, 1] measures how well the graph is connected, and is high for well-connected graphs
such as cliques and expanders but small for graphs that have bottlenecks (such as the dumbbell graph mentioned below). Uniform gossip is slow if the conductance of the network is small, which happens when the graph has bottlenecks. In such a case, uniform gossip can take as much as Θ(𝑛 log 𝑛) rounds.3 For example, consider a dumbbell graph with two cliques each of size 𝑛/2 connected by an edge; here uniform gossip will take Θ(𝑛 log 𝑛) rounds (w.h.p.), even though the graph diameter is only 3. To mitigate the slowness of uniform gossip in graphs of low conductance, a series of papers studied non-uniform gossip that could overcome communication bottlenecks. In non-uniform gossip, it is not required that a node contacts a random neighbor in a round; rather, any (one) neighbor can be contacted. The first such significant result was a non-uniform gossip algorithm by Censor-Hillel and Shachnai [4, 5] that achieved a running time that depended on so-called weak conductance of the graph, which can be substantially larger than its conductance. The weak conductance of a graph, denoted by Φ𝑐 , is parameterized by 𝑐 ⩾ 1, and measures the conductance restricted to node subsets of size up to 𝑛/𝑐 (see Section 2.1 for a formal definition). For example, the conductance (which is the same as weak conductance with 𝑐 = 1) of the above dumbbell graph is small — Θ(1/𝑛 2 ) — but its weak conductance Φ𝑐 is Θ(1) for 𝑐 = 2. The Censor-Hillel-Shachnai algorithm achieves rumor spreading in 𝑂 (
𝑐 log 𝑛 2 Φ𝑐 + 𝑐 ) rounds (with high probability) for any
𝑐 > 1. Hence, for the dumbbell graph, this algorithm takes 𝑂 (log 𝑛) rounds, which is exponentially faster than uniform 1 For example, in dense graphs with Θ(𝑛 2 ) edges and having constant conductance, uniform gossip takes 𝑂 (log 𝑛) rounds and, hence, 𝑂 (𝑛 log 𝑛)
messages, whereas flooding takes Θ(𝑛 2 ) messages. 2W.h.p. stands for with high probability and denotes 1 − 1/𝑛𝑑 , for an arbitrary 𝑑 ⩾ 1. 3 Note that even a weaker version of gossip called push-gossip where only nodes (with the rumor) push, achieves rumor spreading in 𝑂 (𝑛 log 𝑛) rounds [12]. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
3
gossip. An important point to note about this algorithm is that the messages sent can be of very large size (up to linear in 𝑛 due to the fact that a message can consist of the identities of a linear number of nodes) and hence the message overhead is very large even to spread a single rumor. A subsequent work by Censor-Hillel, Haeupler, Kelner, and Maymounkov [2] presented a non-uniform gossip algorithm that runs in time that is independent of the conductance of the graph. This algorithm ran in 𝑂 (𝐷 + polylog 𝑛) rounds (with high probability), where 𝐷 is the graph diameter. This is near optimal since Ω(𝐷) is a trivial lower bound even for the more powerful flooding algorithm (where a node can send messages to all its neighbors in a round). Thus, it was surprising that gossip, which is constrained to contact only one neighbor, can almost (up to an additive polylog 𝑛 term) match the bound obtained by flooding. Hence, this work established that gossip is almost as powerful as flooding. Later, Haeupler [21, 22] showed that the diameter running time bound can even be achieved deterministically, by presenting a deterministic non-uniform gossip algorithm that ran in 2(𝐷 log 𝑛 + log2 𝑛) rounds. It is important to note that all the above gossip algorithms also use messages of large size (at least linear in 𝑛). To summarize, while the above gossip algorithms can be significantly faster than uniform gossip, a main drawback of the algorithm is that they use large-sized messages to spread even a single rumor. (In contrast, in uniform gossip, only the rumor is exchanged, and hence, the message size is small.) This undermines the light-weight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in 𝑛, the network size. Hence, a fundamental question is: Can we achieve fast rumor spreading (in terms of weak conductance or just in terms of the diameter as in the results discussed above) using only small (i.e., polylog 𝑛 size) messages? In this paper, we answer the above question in the affirmative and present two gossip algorithms that achieve fast rumor spreading using messages of polylog 𝑛 size. 1.1
Model
We assume that we are given a connected arbitrary graph 𝐺 = (𝑉 , 𝐸) as input. Let |𝑉 | = 𝑛 and |𝐸| = 𝑚. Each node has a unique ID (identifier) taken from the range [1, 𝑁 ], where 𝑁 is a polynomial in 𝑛. Each ID can be represented using 𝑂 (log 𝑛) bits. As is standard in prior non-uniform gossip algorithms [2, 4, 5, 21, 22], we assume that each node knows its own ID and the IDs of its neighbors. (This is a standard model in distributed computing, called the Knowledge-Till-Radius 1 (𝐾𝑇 1) model.) It is important that the network topology 𝐺 is unknown to the nodes. We assume all nodes have knowledge of the polynomial upper bound 𝑁 . Additionally, the algorithm in Section 4 requires extra knowledge assumptions, which are mentioned in the Preliminaries in Section 2.1. The computation proceeds in synchronous rounds. We assume a gossip-based communication model which is very lightweight, where in a round, a node contacts at most one of its neighbors in order to send and receive a message over that edge. This setting is henceforth known as the GOSSIP model [2, 4, 5, 21, 22]. Note that although the GOSSIP model allows each node to send a message to only one neighbor per round, one can easily simulate sending messages to any 𝑘 ⩾ 1 neighbors in a round, by performing gossip for 𝑘 rounds and thus blowing up the number of rounds by a factor of 𝑘. On the other hand, in the standard CON GEST model, a node can send a message (of small size, say 𝑂 (log 𝑛) bits) to all (or a subset) of its neighbors in a round. In addition, in the LOCAL model, the message size is unbounded, i.e., a node can send messages of arbitrary size to all (or a subset) of its neighbors in a round. As mentioned earlier, prior non-uniform algorithms [4, 5, 21, 22] transmit messages of large (up to linear in 𝑛) size. Hence, they can be said to operate in the GOSSIP − LOCAL model where each node can contact only one Manuscript submitted to ACM
4
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
neighbor in a round, but the size of the message exchanged can be arbitrary. On the other hand, our algorithms operate in the GOSSIP − CON GEST model, where each node can contact only one neighbor in a round, but the size of the message exchanged is small (polylog 𝑛 size).4 Thus, a round 𝑟 in the GOSSIP − CON GEST model consists of the following three steps: (i) each node contacts one neighbor, (ii) each node sends a 𝑂 (polylog 𝑛) bit message to the contacted neighbor and receives a 𝑂 (polylog 𝑛) bit reply, and (iii) after all messages in transit have been received, 𝑢 performs some local computation.5 1.2
Our Contributions
We present two gossip algorithms that achieve fast rumor spreading using messages of polylog 𝑛 size, improving over prior results. Notice that each round in a gossip algorithm results in 𝑂 (𝑛) messages, so the total message complexity of a 𝑡 round algorithm is 𝑂 (𝑛𝑡). A gossip algorithm as a function of weak conductance. (cf. Section 4) We present the first (non-uniform) gossip algorithm to achieve fast rumor spreading in terms of weak conductance using messages of polylog 𝑛 size, in the GOSSIP − CON GEST model. Our (randomized) gossip algorithm for rumor spreading, with high probability, runs in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds for every 𝑐 ⩾ 1, where Φ𝑐 is the weak conductance (defined in Section 2.1). This bound not only improves over the running log 𝑛
time bound of 𝑂 (𝑐 Φ𝑐 + 𝑐 2 ) of Censor-Hillel and Shachnai [4, 5], but also uses significantly smaller messages of polylog 𝑛 size. In other words, while the Censor-Hillel-Shachnai algorithm runs in the GOSSIP − LOCAL model, our algorithm has better performance and runs in the GOSSIP − CON GEST model. A comparison of our result and past work can be found in Table 1. Formally, we show the following result. Theorem 1.1. There exists a GOSSIP − CON GEST algorithm solving rumor spreading, with high probability, in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds with high probability, for every 𝑐 ⩾ 1 and where Φ𝑐 is the weak conductance of the graph. Additionally, one may see that our algorithm is existentially asymptotically optimal. Consider the following variant of the 𝑐-barbell (see Figure 1): consider 𝑐 expanders, each of size 𝑛/𝑐 and diameter Θ(log(𝑛/𝑐)), connected in a line. Such a graph has weak conductance Φ𝑐 = Θ(1) (see Section 2.1). The diameter of such a graph is Θ(𝑐 log(𝑛/𝑐)) and acts as a natural lower bound for gossip. Then, we can see that our algorithm is asymptotically optimal for constant values of 𝑐 and almost asymptotically optimal (up to a log 𝑛 factor) for larger values of 𝑐. Furthermore, the absence of a 𝑐 2 factor in our run time can result in significant time savings for some types of graphs. In particular, for larger values of 𝑐, i.e., 𝑐 = Θ(𝑛), the above described lower bound graph leads to a Θ(𝑛) speedup in run time of our algorithm over that of Censor-Hillel and Shachnai [4, 5]. Table 1. Comparison of gossip algorithms focused on weak conductance Φ𝑐 . 𝑂˜ notation hides logarithmic in 𝑛 factors, where 𝑛 is the number of nodes. Result Censor-Hillel & Shachnai [4, 5]
Run Time (in rounds) log 𝑛 𝑂 (𝑐 Φ𝑐 + 𝑐 2 )
This work - Theorem 1.1
𝑂 (𝑐 Φ𝑐 )
log 𝑛
Message Size Required (in bits) 𝑂˜ (𝑛) 𝑂˜ (1)
4 Note that one can restrict each message size to 𝑂 (log 𝑛) bits instead of 𝑂 (polylog 𝑛) bits; however, this leads to (only) a 𝑂 (polylog 𝑛) -factor blow up
in the round complexity of our algorithms. 5 Note that although each node contacts only one neighbor, a node can be contacted by as many neighbors as its degree in a round (e.g., the center node in a star graph). As standard in gossip protocols (including those that we compare here) [3–5, 7–10, 14, 25], we assume that the node replies to all of them in the same round. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
5
A gossip algorithm as a function of diameter. (cf. Section 3) We also present another gossip algorithm for rumor √ spreading in the GOSSIP − CON GEST model that depends on the network diameter, which runs in 𝑂˜ (𝐷 + 𝑛) rounds with high probability. The randomized gossip algorithm of Censor-Hillel, Haeupler, Kelner, and Maymounkov [2] (see also the deterministic algorithm due to Haeupler [21, 22] with a similar time bound) whose run time is a function of the graph diameter (and not conductance) — takes 𝑂 (𝐷 + polylog 𝑛) rounds, but again, it uses large-sized messages, hence it works only in the GOSSIP − LOCAL model. On the other hand, the randomized gossip algorithm of √ Ghaffari and Kuhn [14] works in the GOSSIP − CON GEST model but takes 𝑂˜ ( 𝑛𝐷) rounds. In this work, we give a randomized gossip algorithm that significantly improves on that latter result. A comparison of our result and past work can be found in Table 2. Theorem 1.2. There exists a GOSSIP − CON GEST algorithm solving rumor spreading, with high probability, in √ ˜ 𝑂 (𝐷 + 𝑛) rounds. √ We note that our algorithm (unlike that of [14]) is optimal for when 𝐷 = Ω( 𝑛). A major open question is whether the bound shown in Theorem 1.2 is optimal. We conjecture that this bound is indeed optimal (up to logarithmic factors) — see Section 6. Table 2. Comparison of gossip algorithms focused on diameter 𝐷. 𝑂˜ notation hides logarithmic in 𝑛 factors, where 𝑛 is the number of nodes. Result Censor-Hillel, Haeupler, Kelner, & Maymounkov [2, 3] Haeupler [21, 22] Ghaffari & Kuhn [14] This work - Theorem 1.2
Run Time (in rounds) 𝑂˜ (𝐷 ) 𝑂˜√(𝐷 ) 𝑂˜ ( 𝑛𝐷 ) √ 𝑂˜ (𝐷 + 𝑛)
Message Size Required (in bits) 𝑂˜ (𝑛) 𝑂˜ (𝑛) 𝑂˜ (1) 𝑂˜ (1)
Applications. (cf. Section 5) Our rumor spreading algorithms can also be used to directly compute certain aggregate functions efficiently in the GOSSIP − CON GEST model. For example, it is easy to compute minimum (or maximum) by simply spreading and aggregating the minimum value (there is no congestion due to the aggregation of different values at nodes). A byproduct of our gossip algorithms is that they construct a spanning tree of the underlying network whose diameter is bounded by the algorithm’s run time. This can be used for various applications. For example, the spanning tree leads to gossip algorithms for other fundamental distributed computing problems such as leader election (where the goal is to elect a unique node in the graph as a leader) and a minimum spanning tree (MST) as well as computing aggregate functions such as sum and count exactly. Corollary 1.3. There exist GOSSIP − CON GEST algorithms solving spanning tree construction, leader election, and aggregate function computation in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds with high probability, for every 𝑐 ⩾ 1 and where Φ𝑐 is the weak conductance of the graph. Corollary 1.4. There exist GOSSIP − CON GEST algorithms solving MST construction, leader election, and √ aggregate function computation, with high probability, in 𝑂˜ (𝐷 + 𝑛) rounds. 1.3
Technical Overview
Rumor Spreading on Weak Conductance Graphs. (see Section 4) As noted earlier, one of the difficult challenges involved with spreading a message in a graph is dealing with communication bottlenecks. Consider again the example Manuscript submitted to ACM
6
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
of a dumbbell graph. While it may be simple and fast to spread messages within each of the individual cliques, the difficulty arises in finding the very few edges that belong to the cut set between the cliques. This is where the powerful technique of graph sketching [1] turns out to be useful. By rapidly aggregating certain information within a clique, we can with high probability find one of the edges leading out of it. More generally, instead of a clique, suppose we have a high conductance component, of conductance Φ𝑐 for some known 𝑐. In fact, let us decompose the graph into disjoint sets of high conductance components with edges between them. In such a graph, we can rapidly spread information within each such high conductance component, then use sketching to find inter-component edges and continue to spread the rumor. One might assume then that if there are 𝑐 such components, it would only take 𝑂 (𝑐𝑇 ) time to spread the rumor over the whole graph, where 𝑇 is the total time to spread the rumor within a given high conductance component and subsequently perform graph sketching. However, an important subtlety of graph sketching stops us here. That subtlety is that graph sketching requires centralized aggregation of information at a node. Thus, if we want to find the outgoing edge out of a super cluster of the graph, consisting of two or more components/clusters with inter-cluster edges, we must aggregate the information from all nodes within these components, which may take time proportional to the diameter of that super cluster. Imagine the supergraph with these components as nodes and inter-component edges as edges. If such a supergraph forms a line, then it is easy to see that a naive implementation of rumor spreading may result in the super cluster containing the rumor only growing by one cluster with every instance of graph sketching. Thus, the algorithm may take 𝑂 ((1 + 2 + 3 + . . . + 𝑐 − 1)𝑇 ) = 𝑂 (𝑐 2𝑇 ) time to spread the rumor to all nodes. Thus, we must be a bit more careful with the growth of the super cluster. To overcome the above issue, we control the diameter of the super clusters that perform graph sketching such that in phase 𝑖, only super clusters with diameter at most 2𝑖 in the supergraph perform graph sketching. We complement this by showing that the size of the super clusters also grows exponentially, so that after log 𝑐 phases, all clusters in the supergraph belong to one super cluster and thus the rumor has been spread to all nodes. The time then to perform this would be 𝑂 ((1 + 2 + 22 + 23 + . . . + 2log 𝑐 )𝑇 ) = 𝑂 (𝑐𝑇 ). Rumor Spreading on General Graphs. (see Section 3) A natural approach for solving rumor spreading in GOSSIP − CON GEST within general graphs (see, e.g., [14]) is to sparsify the communication graph 𝐺. However, such a sparsification must run fast even with the lightweight communication of GOSSIP − CON GEST — that is, with communication over only 𝑂 (𝑛) edges per round. A well-known sparsification technique consists of separating the nodes of 𝐺 into two sets according to some (parameter) degree threshold Δ𝑇 ℎ , say 𝐻 for the high degree node subset and 𝐿 for the low degree node subset. (This can be done given only the nodes’ initial knowledge of their degree.) Then, by definition the set of edges incident to 𝐿 is already somewhat sparse, since it contains 𝑂 (𝑛Δ𝑇 ℎ ) edges. As for the remainder of 𝐺, a fast sparsification method is the following. First, sample uniformly at random some 1/Δ𝑇 ℎ fraction of the nodes in 𝑉 , which we call stars, and have each high degree node join the cluster of any neighboring star node, if one exists. (Finding such a neighbor requires only sampling 𝑂 (Δ𝑇 ℎ log 𝑛) neighbors, hence is relatively fast even in GOSSIP − CON GEST .) These star clusters are then merged together using any classical tree-merging algorithm (e.g., Boruvka’s algorithm), within which outgoing edges are found efficiently via graph sketches. In other words, we compute a maximal forest over the high degree parts of 𝐺, with one nice property: the sum of the diameter of the forest’s trees is bounded by 𝑂 (𝑛 log 𝑛/Δ𝑇 ℎ ) w.h.p. The resulting sparse graph also, crucially, satisfies some stretch properties: (1) large additive stretch of 𝑂 (𝑛 log 𝑛/Δ𝑇 ℎ ) on shortest paths within the high degree parts of 𝐺, and (2) no stretch on the shortest paths within the low degree parts Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
7
of 𝐺. However, the rumor does not spread efficiently throughout all parts of that sparse graph. Indeed, although the rumor spreads by one hop along the computed maximal forest, the rumor spreads more slowly along the edges incident to 𝐿 (with a multiplicative factor blow-up in in the degree Δ𝑇 ℎ ). As a result, the rumor spreading takes 𝑂˜ (Δ𝑇 ℎ 𝐷 +𝑛/Δ𝑇 ℎ ) rounds. By optimizing Δ𝑇 ℎ , one can trade off the slow down from a larger additive stretch with the slow down from the √ degree of nodes in 𝐿. Such an optimization leads, essentially, to the 𝑂˜ ( 𝑛𝐷) runtime obtained by [14]. In this work, we push this natural sparsification strategy one step further. More concretely, we sparsify the subgraph in such a way that the maximum degree over the low degree parts is significantly reduced — in fact, down to a maximum degree of 𝑂 (log 𝑛). To do so, we accept one minor trade-off: a 𝑂 (log 𝑛) multiplicative stretch on the shortest paths over the low degree parts. Through an efficient simulation of the CON GEST model, this additional sparsification step takes only 𝑂˜ (Δ𝑇 ℎ ) rounds, after which the additional properties satisfied by our sparsification technique directly √ ensure that rumor spreading takes only 𝑂˜ (𝐷 + 𝑛/Δ𝑇 ℎ + Δ𝑇 ℎ ) rounds. Optimizing Δ𝑇 ℎ leads to our 𝑂˜ (𝐷 + 𝑛) runtime.
1.4
Related Work and Comparison
Gossip and rumor spreading protocols have been studied extensively for many decades starting with the work of Frieze and Grimmett [13], and then Pittel [30]. We restrict ourselves to those that are most relevant to this work and refer to prior works [2, 4, 5, 21, 22] and the references therein for a good survey of related work. Rumor spreading has been studied with respect to spreading a rumor from a single node as well as spreading a rumor from each node in the network (or all-to-all rumor spreading). Much of the original research on rumor spreading considered spreading a single rumor according to the uniform gossip process on a complete graph where it was shown that it took 𝑂 (log 𝑛) rounds [13, 30]. The work of Karp, Schindelhauer, Shenker, and Vocking [25] studied uniform and non-uniform (push-pull) gossip algorithms for the complete graph and showed upper and lower bounds on the total message complexity with respect to the round complexity. Chierichetti, Lattanzi, and Panconesi [8] showed that uniform gossip gives fast rumor spreading in expander graphs (which are graphs with constant conductance) and log4 𝑛
more generally in 𝑂 ( Φ6 ) rounds in graphs of conductance Φ. This was improved to
log2 ( Φ1 ) log 𝑛 by the same set of Φ
authors [7] and finally to 𝑂 (log 𝑛/Φ) rounds by Giakkoupis [15] (see also [6]). This bound in terms of conductance is in general tight [6, 15]. It is important to note that the above uniform gossip algorithm uses small messages to spread a (single) rumor: in particular, only the rumor is exchanged over any edge. No IDs, etc., are sent as part of messages. Hence, according to our model (Section 1.1), it works in the GOSSIP − CON GEST model. Since the performance of uniform gossip is tied to the conductance of the graph, its run time is slow when the conductance is small. Graph with bottlenecks (e.g., dumbbell) have small conductance, despite having a small diameter. To address this, as mentioned earlier, Censor-Hillel and Shachnai [4, 5] defined the notion of weak conductance Φ𝑐 and gave a gossip-based rumor spreading algorithm whose run time is determined by Φ𝑐 (for all 𝑐 ⩾ 1). For many graphs such as the dumbell, Φ𝑐 is significantly smaller than the conductance Φ. This algorithm is more sophisticated than uniform gossip and cleverly avoids sending too many messages to neighbors who have already received the rumor. But to accomplish this saving, the algorithm uses large-sized messages, up to linear in 𝑛, since a message can contain all the IDs of the nodes (informally, the IDs help a node to identify its neighbors who have already gotten the message without the need to communicate). This is the situation when the goal is to spread even a single rumor. We improve on this work, both in terms of running time, and more importantly, by using small-sized messages. Manuscript submitted to ACM
8
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
Subsequent works [2, 3, 21, 22] presented gossip algorithms that ran in time that is independent of the conductance of the graph — in 𝑂 (𝐷 + polylog 𝑛) rounds (with high probability) [2, 3] and in 𝑂 (𝐷 log 𝑛 + log2 𝑛) [21, 22], where 𝐷 is the graph diameter. This is near optimal since Ω(𝐷) is a trivial lower bound even for non-gossip algorithms (where a node can send a message to all of its neighbors in a round).
√ Ghaffari and Kuhn [14] presented a gossip algorithm running in 𝑂˜ ( 𝑛𝐷) rounds to spread a rumor in the GOSSIP − √ CON GEST model. We improve over this work by presenting a gossip algorithm running in 𝑂˜ (𝐷 + 𝑛) rounds in the GOSSIP − CON GEST model.
2
Preliminaries
We start by presenting the following standard Chernoff bounds, which we use in Section 3. Lemma 2.1 (Chernoff Bounds [27]). Let 𝑋 1, . . . , 𝑋𝑘 be independent {0, 1} random variables. Let 𝑋 denote the sum of the random variables, 𝜇 the sum’s expected value and 𝜇𝐿 , 𝜇𝐻 be any value respectively smaller and greater than 𝜇. Then, (1) Pr[𝑋 ⩽ (1 − 𝛿)𝜇𝐿 ] ⩽ exp(−𝛿 2 𝜇𝐿 /2) for 0 ⩽ 𝛿 ⩽ 1, (2) Pr[𝑋 ⩾ (1 + 𝛿)𝜇𝐻 ] ⩽ exp(−𝛿 2 𝜇𝐻 /3) for 0 ⩽ 𝛿 ⩽ 1, (3) Pr[𝑋 ⩾ (1 + 𝛿)𝜇𝐻 ] ⩽ exp(−𝛿 2 𝜇𝐻 /(2 + 𝛿)) for 𝛿 ⩾ 1. Next, we give several definitions related to a relaxation of conductance. The relaxed conductance notion — that of weak conductance — was first introduced in [4, 5], and leads to a natural decomposition into clusters with weak conductance. That decomposition is implicitly used in [4, 5], but we define it explicitly, as it both helps describe our algorithms and may be of independent interest. Next, in Section 2.2, we define graph sketches. Finally, in Section 2.3, we describe several well-known distributed computing primitives, including some that use graph sketches, but adapted to the GOSSIP − CON GEST model. 2.1
Conductance and Weak Conductance
For any 𝑆 ⊆ 𝑉 , the conductance of the cut (𝑆,𝑇 = 𝑉 \ 𝑆) is 𝜙 (𝑆,𝑇 ) = |𝑐𝑢𝑡 (𝑆,𝑇 )|/min{𝑣𝑜𝑙 (𝑆), 𝑣𝑜𝑙 (𝑇 )}, where 𝑣𝑜𝑙 (𝑆) is the sum of the degrees of all nodes in 𝑆, and 𝑐𝑢𝑡 (𝑆,𝑇 ) denotes the set of all edges with one vertex in 𝑆 and one vertex in 𝑇 = 𝑉 − 𝑆. Then, the conductance over the graph 𝐺 is naturally defined as: Φ(𝐺) = min 𝜙 (𝑆, 𝑉 \ 𝑆) 𝑆 ⊆𝑉
The conductance Φ(𝐺) captures how fast information can be spread from one node to all other nodes in graph 𝐺. If one only wants to spread the information to at least 𝑛/𝑐 nodes (for some constant 𝑐 > 1), then a weaker definition can be used. More concretely, for any value 𝑐 ⩾ 1, we can define the weak conductance as in [4, 5]: Φ𝑐 (𝐺) = min max min 𝜙 (𝑈 , 𝑆 𝑣 \ 𝑈 ) 𝑣 ∈𝑉
𝑆 𝑣 ⊆𝑉 , 𝑈 ⊆𝑆 𝑣 𝑆 𝑣 ∋𝑣, |𝑆 𝑣 |⩾𝑛/𝑐
Whenever 𝐺 is clear from the context, we simply say Φ and Φ𝑐 . An illustrative example of the difference between conductance and weak conductance is to consider a 𝑐-barbell graph (see [4, 5] and Figure 1) where 𝑐 cliques 𝐶 1, 𝐶 2, . . . , 𝐶𝑐 , each of size 𝑛/𝑐, connected in a line such that between cliques 𝐶𝑖 and 𝐶𝑖+1 , 1 ⩽ 𝑖 ⩽ 𝑐 − 1, there is one edge between a single node in 𝐶𝑖 and a single node in 𝐶𝑖+1 . In this graph, Φ𝑐 = Θ(1) while the overall conductance is Φ = Θ(𝑐/𝑛 2 ). Notice that for any real value 𝑘 ∈ [1, 𝑐), Φ𝑘 = 𝑂 (𝑘𝑐/𝑛 2 ) whereas for any 𝑘 ⩾ 𝑐, Φ𝑘 = Ω(1). Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
9
Fig. 1. A 𝑐-barbell of 𝑛 nodes. There are 𝑐 cliques, each containing 𝑛/𝑐 nodes, connected in a path.
The above definition implies that any graph 𝐺 with weak conductance Φ𝑐 , for some value of the parameter 𝑐 ⩾ 1, satisfies the following (structural) property. For each node 𝑣, there exists some maximal connected component that contains 𝑣, of size at least 𝑛/𝑐, and with conductance at least Φ𝑐 . (Here, maximal is meant in the sense the component is not contained within any other such connected component.) We call the union of all such maximal components of 𝑣, the maximal spreading component of 𝑣, and emphasize that via the result of Giakkoupis [15], broadcast (and information spreading for LOCAL) can be done in 𝑇 = 𝑂 (log 𝑛/Φ𝑐 ) rounds within that component. For the algorithm in Section 4, we assume that every node knows the values of both 𝑐 and Φ𝑐 . We note that the previous best algorithm for this setting [4, 5] needs this assumption in order to achieve termination. (Weak) Sunflowers and (Weak) Sunflower Decomposition. We provide a decomposition of the graph, with a terminology inspired from the sunflower set systems used in the famous sunflower lemma proved by Erdös and Rado in [11]. For any node 𝑣, we can consider all maximal spreading components (from any node 𝑢 ≠ 𝑣) that intersect with the maximal spreading component of 𝑣. We call the union of all such maximal spreading components the (weak) sunflower of 𝑣. Moreover, we refer to the maximal spreading component of 𝑣 as its kernel, and to the other intersecting components as its petals. (Note that kernels and petals here differ from those in sunflower set systems, since different petals may intersect different subsets of the kernel.) Weak sunflowers can be used to decompose the communication graph 𝐺, with major implications for the design of rumor-spreading algorithms in the GOSSIP − CON GEST model. More precisely, we show that you can decompose the graph 𝐺 into at most 𝑗 ⩽ 𝑐 sunflowers, associated respectively with nodes 𝑣 1, 𝑣 2, ..., 𝑣 𝑗 , such that the maximal spreading components of 𝑣 1, 𝑣 2, ..., 𝑣 𝑗 are pairwise disjoint and the union of the sunflowers covers the whole graph. Lemma 2.2. Any graph 𝐺 with weak conductance Φ𝑐 , for some value of the parameter 𝑐 ⩾ 1, can be decomposed into at most ⌊𝑐⌋ pairwise kernel-disjoint sunflowers. Proof. The decomposition can be obtained constructively as follows. Let S be a collection of sunflowers, initially empty. Then, take any arbitrary node 𝑣 1 , compute its sunflower 𝑆 1 and add 𝑆 1 to S. After which, as long as there remains some node outside S, find such a node 𝑣𝑖 (i.e., some node 𝑣𝑖 ∈ 𝑉 such that 𝑣𝑖 ∉ 𝑆, ∀𝑆 ∈ S), compute its sunflower 𝑆𝑖 in graph 𝐺 and add 𝑆𝑖 to S. Note that this procedure computes pairwise kernel-disjoint sunflowers, otherwise the maximal spreading component of node 𝑣𝑖 would be in a prior sunflower. As such, for each sunflower in S, each kernel must contain at least ⌈𝑛/𝑐⌉ ⩾ 𝑛/𝑐 unique nodes, and thus |S| ⩽ 𝑐. Since |S| is an integer, in fact it holds that |S| ⩽ ⌊𝑐⌋. In other words, the procedure computes at most ⌊𝑐⌋ pairwise kernel-disjoint sunflowers that cover graph 𝐺.
□
We emphasize that the decomposition is in general not unique. In particular, in the proof there may be many different choices for the node sequence 𝑣 1, 𝑣 2, ..., 𝑣 𝑗 , where 𝑗 ⩽ 𝑐. Moreover, we also point out that although the sunflowers are (pairwise) kernel-disjoint, their petals (and thus the sunflowers themselves) may not be disjoint. Manuscript submitted to ACM
10
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
2.2
Graph Sketches
Consider an arbitrary set of nodes 𝑉 , such that all nodes of 𝑉 have unique IDs in [1, 𝑁 ], where 𝑁 is known to all nodes. We define, for any graph 𝐺 = (𝑉 , 𝐸) and node 𝑣 ∈ 𝑉 , the incidence vector i𝐺 (𝑣) ∈ R ( 2 ) whose entries correspond to all 𝑁
possible choices of two IDs in 𝑁 . An entry in i𝐺 (𝑣) corresponding to the possible edge between 𝑢 with 𝑖𝑑𝑢 ∈ 𝑁 and 𝑣 is 0 if (𝑢, 𝑣) ∉ 𝐸, 1 if (𝑢, 𝑣) ∈ 𝐸 and 𝑖𝑑𝑢 > 𝑖𝑑 𝑣 , and −1 otherwise (i.e., (𝑢, 𝑣) ∈ 𝐸 and 𝑖𝑑𝑢 < 𝑖𝑑 𝑣 ). Entries in i𝐺 (𝑣) that correspond to a possible edge not including 𝑣 (e.g., (𝑢, 𝑤)) have value 0. Naturally, one can extend this definition to any Í node subset 𝑆 ⊆ 𝑉 : more precisely, i𝐺 (𝑆) = 𝑣 ∈𝑆 i𝐺 (𝑣). Note that by linearity, the non-zero indices of i𝐺 (𝑆) indicate exactly which edges are in the cut of 𝑆 with respect to 𝐺, that is, in 𝐸𝐺 (𝑆, 𝑉 \ 𝑆). One may use the incidence vector of some node set 𝑆 to sample an outgoing edge from 𝑆, if one exists, uniformly at random from all such outgoing edges, i.e., sample a non-zero entry in i𝐺 (𝑆) uniformly at random. However, in a distributed setting, to compute the incidence vector on a set of nodes 𝑆, one would need to aggregate the incidence vectors of the nodes belonging to 𝑆. This is problematic since incidence vectors are exponentially larger (recall that they have size 𝑁2 ) than our 𝑂 (polylog 𝑁 ) message size. 𝑁 Fortunately, we can use a linear sketch [1] — a well-chosen linear function from R ( 2 ) to R𝑘 — or in other words, a graph sketching matrix — a well-chosen 𝑘 × 𝑁2 size matrix 𝑀𝐺 — to compress these vectors (i𝐺 (𝑣)) 𝑣 ∈𝑉 into smaller (sketch) vectors ( s𝐺 (𝑣)) 𝑣 ∈𝑉 of size 𝑘 = 𝑂 (polylog 𝑁2 ); more concretely, 𝑀𝐺 · i𝐺 (𝑣) = s𝐺 (𝑣). Moreover, although this compression necessarily loses some information, it has two major advantages. First, it is possible to sample (almost) 𝑁 uniformly at random one of the non-zero indices of i𝐺 (𝑣) ∈ R ( 2 ) by performing operations on s𝐺 (𝑣) only (albeit with some small failure probability). More concretely, for any graph sketching matrix 𝑀𝐺 and for any subset 𝑆 ⊆ 𝑉 , there exists a sampling function 𝑓𝐺 that takes the sketch vector s𝐺 (𝑆) as input and outputs an edge chosen uniformly at random in 𝐸𝐺 (𝑆, 𝑉 \ 𝑆). Second, the linearity of the graph sketching matrix allows us to compute s𝐺 (𝑆) without computing i𝐺 (𝑆), but instead by computing the sketch vectors ( s𝐺 (𝑣)) 𝑣 ∈𝑆 and summing them. In summary, for any subset 𝑆 ⊆ 𝑉 , we can sample an edge chosen uniformly at random in 𝐸𝐺 (𝑆, 𝑉 \ 𝑆) by (i) having nodes agree on Θ(log2 𝑛) true random bits that they can use to locally compute a common graph sketching matrix 𝑀𝐺 with polynomially bounded integer entries [24, 28], (ii) aggregating the sketch vectors of all nodes in 𝑆, and (iii) applying the sampling function 𝑓𝐺 on the aggregate vector s𝐺 (𝑆). Note that these steps require messages of small 𝑂 (polylog 𝑛) size only. A more formal statement is given below, which can be obtained straightforwardly by adapting known results [1, 24, 28]. Lemma 2.3. For any upper bound 𝑁 on the ID range and constant 0 < 𝛿 < 1, there exist a graph sketching matrix 𝑀𝐺 (with entries polynomially bounded in 𝑁 ) and a sampling function 𝑓𝐺 such that for any node subset 𝑆 ⊂ 𝑉 , the aggregate Í sketch vector s𝐺 (𝑆) = 𝑢 ∈𝑆 s𝐺 (𝑢) can be represented using 𝑂 (polylog 𝑛) bits, and 𝑓𝐺 ( s𝐺 (𝑆)) samples a (uniformly) random edge in 𝐸𝐺 (𝑆, 𝑉 \ 𝑆) with probability 1 − 𝛿. 2.3
Communication Primitives in the GOSSIP − CON GEST Setting
The following “basic” distributed primitives (e.g., tree construction, broadcast and convergecast over a tree, etc.) are well-known in other models, such as CON GEST . However, we describe them again here because their description needs to be adapted for the GOSSIP − CON GEST model. We remind that a (distributed) tree is a set of undirected edges of 𝐺 that forms a tree, and such that each node in the tree knows which of its incident edges is in the tree as well as which one of these leads to its parent in the tree. (As a Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
11
result, each node also knows which edge leads to its children in the tree.) Similarly, a (distributed) forest is a union of disjoint (distributed) trees. Moreover, we assume that rumors follow some agreed upon, total ordering. For example, when rumors are nodes’ IDs, the natural total order on IDs is such an ordering. This allows nodes to perform certain aggregation operations on rumors, and thus avoid being slowed down by the limited bandwidth of the GOSSIP − CON GEST model. Tree Construction. In graphs with conductance Φ, rumor-spreading can be done via (a simple modification of) uniform gossip. Recall that in uniform gossip, each node contacts a random neighbor every round, and exchanges the rumor (if any of them have it). Then, the modification is simple. We allow a set of sources nodes, and thus multiple rumors, and we modify the algorithm so that each node exchanges the highest rumor it has seen until now upon every contact (initiated or received). In which case, 𝑂 (log 𝑛/Φ) rounds suffice for the highest rumor to spread (with high probability) over the whole graph, in the GOSSIP − CON GEST model. Lemma 2.4 ([15]). For any 𝑛-node graph 𝐺 = (𝑉 , 𝐸) with conductance Φ, and any set 𝑆 ⊆ 𝑉 of source nodes. Then, the above algorithm spreads the highest rumor to all other nodes in 𝑂 (log 𝑛/Φ) rounds, with high probability. Moreover, another simple modification gives a spanning tree construction algorithm in the GOSSIP −CON GEST model. Assume each source node holds a unique rumor (e.g., an ID). Then, it suffices if whenever a node receives a rumor higher than any it has seen until now, the node takes the sender as its parent (in the tree being constructed). If the highest rumor the node has seen when the rumor-spreading algorithm terminates is the rumor it initially held (if it held any), then that node becomes the root. This simple, modified version of uniform gossip constructs a (distributed) spanning tree of 𝐺 (as defined previously) rooted in the source node with the highest rumor. Corollary 2.5. For any 𝑛-node graph 𝐺 = (𝑉 , 𝐸) with conductance Φ, and at least one source node, the above algorithm constructs a spanning tree rooted at the source node with the highest rumor in 𝑂 (log 𝑛/Φ) rounds, with high probability. Proof. By Lemma 2.4, each node 𝑣 ∈ 𝑉 , 𝑣 ≠ 𝑠 receives the highest rumor (and thus some rumor strictly higher than its own, if it initially held any), in 𝑂 (log 𝑛/Φ) rounds, with high probability. (For the remainder of the proof, we condition on this event happening.) Hence, by the algorithm’s description, each node except the root orients one of its incident edges (toward its parent) upon receiving that highest rumor. Since each node orients the corresponding edge towards another node having received the (same, highest) rumor strictly earlier than itself, these oriented edges cannot form a cycle. The statement (and error probability) follows.
□
If we consider graphs in which only smaller regions have good conductance, such as weak conductance graphs, then the above modified (highest rumor) uniform gossip algorithm allows fast rumor spreading to happen within sunflowers — this essentially follows by Lemma 2.4. Corollary 2.6. Consider some constant 𝑐 ⩾ 1, 𝑛-node graph 𝐺 = (𝑉 , 𝐸) with weak conductance Φ𝑐 , and source node 𝑠 ∈ 𝑉 . Then, after 𝑂 (log 𝑛/Φ𝑐 ) rounds, it holds with high probability that any node 𝑣 in the sunflower of 𝑠 receives some rumor greater or equal to the highest rumor initially held by a node in that sunflower. Proof. It is straightforward to see that Lemma 2.4 also implies that for any subgraph 𝐻 = (𝑉𝐻 , 𝐸𝐻 ) of 𝐺 with conductance Φ′ (with at least one source node), the (modified) uniform gossip algorithm ensures that each node 𝑣 ∈ 𝑉𝐻 receives the highest rumor initially held by some node in 𝑉𝐻 , or some even higher rumor from 𝑉 \ 𝑉𝐻 , in 𝑂 (log 𝑛/Φ′ ) rounds and with high probability. Manuscript submitted to ACM
12
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
Now, for any node 𝑢 in the maximal spreading component of 𝑠, there exists at least one connected component 𝐶 containing 𝑢 and 𝑠, of size at least 𝑛/𝑐 and with conductance at least Φ𝑐 . Then, by the above statement, any node in 𝐶, and thus 𝑢, receives the highest rumor initially held by some node in 𝐶, or some even higher rumor, in 𝑂 (log 𝑛/Φ𝑐 ) rounds and with high probability. We can apply the same reasoning, but now we consider any node 𝑣 in the sunflower of 𝑠. Then, some maximal spreading component intersecting that of 𝑠 must contain 𝑣, and thus there exists some node 𝑢 in that intersection, and at least one connected component 𝐶 ′ containing 𝑢 and 𝑣, of size at least 𝑛/𝑐 and with conductance at least Φ𝑐 . Then, again by the above statement, any node in 𝐶 ′ , and thus both 𝑢 and 𝑣, receives the highest rumor initially held by some node in 𝐶 ′ , or some even higher rumor, in 𝑂 (log 𝑛/Φ𝑐 ) rounds and with high probability. Finally, let 𝑤 be the node holding initially the highest rumor in the sunflower of 𝑠. Then, 𝑠 receives the rumor of 𝑤, or some even higher rumor from outside the sunflower, in 𝑂 (log 𝑛/Φ𝑐 ) rounds and with high probability, by the above. In turn, this implies that after another 𝑂 (log 𝑛/Φ𝑐 ) rounds and with high probability, any node in the sunflower of 𝑠 receives the rumor of 𝑤, or an even higher rumor.
□
However, in weak conductance graphs, a single rumor does not necessarily reach all nodes within 𝑂 (log 𝑛/Φ𝑐 ) rounds. In fact, even within the sunflower of some node 𝑠, although the above corollary implies that all nodes receive some rumor greater or equal to that of 𝑠, it may still happen that different nodes receive different rumors. As such, the above (tree construction) modification of uniform gossip does not give a direct analogue of Corollary 2.5 for weak conductance graphs, or in other words, uniform gossip on weak conductance graphs does not lead to a simple and time-efficient spanning tree construction algorithm. Yet, for any weak conductance graph 𝐺 and any set 𝑆 ⊆ 𝑉 of source nodes, we can time-efficiently (i.e., in 𝑂 (log 𝑛/Φ𝑐 ) rounds) construct a forest rooted in 𝑆 and spanning the union of the sunflowers of nodes in 𝑆, in the GOSSIP − CON GEST model. This comes with a major caveat: the obtained forest may have depth 𝜔 (log 𝑛/Φ𝑐 ), despite the runtime being bounded to 𝑂 (log 𝑛/Φ𝑐 ). This is because even though a single rumor can create a branch of at most 𝑂 (log 𝑛/Φ𝑐 ) nodes in the computed forest, one branch may result from the propagation of multiple, different rumors. Corollary 2.7. Consider some constant 𝑐 ⩾ 1, 𝑛-node graph 𝐺 = (𝑉 , 𝐸) with weak conductance Φ𝑐 , and set 𝑆 ⊆ 𝑉 of source nodes. Let 𝑈 be all nodes contained in the union of the sunflowers of nodes in 𝑆. Then, 𝑂 (log 𝑛/Φ𝑐 ) rounds suffice to compute some (distributed) forest spanning 𝑈 , with high probability. Proof. By Corollary 2.6, it holds with high probability that each node 𝑣 ∈ 𝑈 , 𝑣 ∉ 𝑆, receives some rumor in 𝑂 (log 𝑛/Φ𝑐 ) rounds. (For the remainder of the proof, we condition on this event happening.) Moreover, nodes in 𝑆 may receive some rumor strictly higher than their own. Any node in 𝑆 for which this does not happen, becomes a root by the algorithm description. Moreover, once again by the algorithm’s description, each non-root node orients one of its incident edges (toward its parent) for the last time upon receiving the highest rumor it sees in the 𝑂 (log 𝑛/Φ𝑐 ) rounds. Now, it follows that each node orients that edge towards some node having received the same rumor in some strictly earlier round, or a strictly higher rumor. In turn, this implies that these oriented edges cannot form a cycle. The statement (and error probability) follows.
□
Broadcast & Convergecast. For these two primitives, consider some distributed forest of root set 𝑆 ⊆ 𝑉 and of depth 𝑇 , where 𝑇 is some known upper bound. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
13
Then, we describe a broadcast primitive over that tree. We assume that any root 𝑠 ∈ 𝑆 has some message 𝜇𝑠 , and that broadcast is successful if for any root 𝑠 ∈ 𝑆, every node in the tree of 𝑠 outputs 𝜇𝑠 . This can be done in 𝑇 rounds, during each of which, each node contacts its parent and receives the broadcast message if its parent already knows it. A simple modification yields a primitive for a partial broadcast up to depth 1 ⩽ 𝑑 ⩽ 𝑇 , described concretely as follows: for any root 𝑠 ∈ 𝑆, every node in the tree of 𝑠 and at depth at most 𝑑 must output 𝜇𝑠 . Indeed, running the broadcast primitive for 𝑑 rounds ensures that every node at depth at most 𝑑 receives the corresponding broadcast message within these rounds. The convergecast primitive works conversely to the broadcast primitive. Now, each node 𝑣 in the forest may start with some message 𝜇 𝑣 , and all nodes know some aggregation function (e.g., min, max, sum and average) for these messages. Then, in each of the 𝑇 rounds, once a node 𝑣 has received a message from each of its children, it aggregates these messages with its own message 𝜇 𝑣 . If the node is not the root, then it contacts its parent, and sends it that aggregate. Otherwise, 𝑣 outputs the aggregate. Proposition 2.8. For any 𝑛-node graph 𝐺 and depth-𝑇 (distributed) forest, where 𝑇 is some known upper bound, broadcast and convergecast over the forest can be done in 𝑂 (𝑇 ) rounds. Moreover, for any integer 1 ⩽ 𝑑 ⩽ 𝑇 , partial broadcast up to depth 𝑑 can be done in 𝑂 (𝑑) rounds. Sampling Outgoing Edges. Once again, consider some distributed forest with root set 𝑆 ⊆ 𝑉 and of depth 𝑇 , where 𝑇 is some known upper bound. We describe how the tree roots can, simultaneously, each sample an outgoing edge (i.e., whose other endpoint is not in the tree), if there exists one, in 𝑂 (𝑇 ) rounds and with high probability. This is done by relying on graph sketches, which are described in Section 2.2. A tree root creates a common random string of 𝑂 (polylog 𝑛) bits and broadcasts that string to all nodes in its tree (using the above described broadcast primitive). After which, each node in the tree creates some 𝑂 (log 𝑛) graph sketches (using their incidence vectors and that common random string) and convergecasts them to the root. (Note that during the convergecast, graph sketches are aggregated, but since each node has a single parent in the tree, the same graph sketch is not aggregated twice.) Finally, the root samples some outgoing edge (with high probability) and broadcasts that edge to all nodes in its tree. Proposition 2.9. For any 𝑛-node graph 𝐺 and depth-𝑇 forest, where 𝑇 is some known upper bound, each (distributed) tree’s roots can sample an outgoing edge in 𝑂 (𝑇 ) rounds, with high probability. 3
Rumor Spreading in General Graphs
A natural approach for solving rumor spreading in GOSSIP − CON GEST within general graphs — see e.g. [14] — is to sparsify the communication graph 𝐺. Then, one must trade off the cost of computing a sparse subgraph 𝐺 ′ of 𝐺 with the stretch properties of 𝐺 ′ . Clearly, the latter properties impact the runtime of any rumor spreading algorithm run on 𝐺 ′ , since rumor spreading will take at least the diameter of 𝐺 ′ . However, we do not have any fast sparsification methods in GOSSIP − CON GEST to compute a sparse subgraph with low stretch over the entire graph. Instead, we can, at a reasonable runtime cost, compute a sparse subgraph 𝐺 ′ with the following stretch properties: (1) large additive stretch on shortest paths within the high degree parts of 𝐺, and (2) low (or even no) multiplicative stretch on the shortest paths within the low degree parts of 𝐺. In this work, we extend this sparsification approach one step further, with the following intuition in mind: the runtime of simple rumor spreading on 𝐺 ′ depends not only on the stretch properties of 𝐺 ′ , but also on its degree Manuscript submitted to ACM
14
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
properties. More precisely, in addition to the above stretch properties, our computed sparse subgraph 𝐺 ′ ensures (informally) that on the low (but polynomial in 𝑛) degree parts of 𝐺, 𝐺 ′ also has 𝑂 (log 𝑛) maximum degree. In Section 3.1, we show how to simulate one round of CON GEST communication with a degree dependent, multiplicate blowup in GOSSIP − CON GEST . Following which, we describe our sparsification technique in Section 3.2. (We leverage the simulation from Section 3.1 to run this sparsification efficiently.) Finally, in Section 3.3, we leverage this new sparsification technique to give an algorithm that achieves rumor spreading, for any 𝑛-node graph 𝐺 of √ diameter 𝐷, in 𝑂˜ (𝐷 + 𝑛) rounds w.h.p., in the GOSSIP − CON GEST model. 3.1
Vertex Cover Based Simulation of CON GEST
In general, communication within the GOSSIP − CON GEST model is significantly more limited than that of the CON GEST model. However, when the communication graph 𝐺 has low maximum degree — e.g., the maximum degree is Δ = 𝑂 (1) — then clearly the GOSSIP − CON GEST model can efficiently simulate any algorithm designed in the CON GEST model. More precisely, one round of CON GEST communication can be simulated via a phase of Δ rounds of GOSSIP − CON GEST communication. During each such phase, each node contacts all of its neighbors one at a time — one neighbor per round and in a round robin fashion. Moreover, the communication exchange between any two nodes 𝑣, 𝑢 simply consists of the messages that 𝑣 and 𝑢 send to each other within the simulated round. We extend the above insight to general communication graphs — see Lemma 3.1 below — in the sense that a “low degree” vertex cover over some subgraph of 𝐺 suffices to efficiently simulate CON GEST communication. We crucially leverage this simulation in Section 3.2. Lemma 3.1. Let 𝐺 ′ = (𝑉 ′, 𝐸 ′ ) be some (possibly disconnected) subgraph of 𝐺. Furthermore, let Δ𝑇 ℎ ⩾ 1 be some integer degree threshold, and 𝑈 be a vertex cover of 𝐺 ′ such that the maximum degree of nodes in 𝑈 within 𝐺 ′ is at most Δ𝑇 ℎ . Then, there exists a GOSSIP − CON GEST algorithm simulating one round of CON GEST communication on the connected components of 𝐺 ′ using 𝑂 (Δ𝑇 ℎ ) rounds. Proof. The GOSSIP − CON GEST algorithm simulating one round of CON GEST communication on the connected components of 𝐺 ′ is straightforward. Nodes outside 𝑈 do not contact any neighbors, whereas nodes in 𝑈 contact all of their neighbors within 𝐺 ′ , one at a time. Since a new neighbor can be contacted per round, this takes at most Δ𝑇 ℎ rounds. Moreover, the communication that happens when some node 𝑣 contacts some neighbor 𝑢 simply consists of an exchange of the messages that 𝑣 and 𝑢 send to each other within the simulated round of CON GEST communication. Finally, the correctness of the simulation follows from the fact that for every edge in 𝐸 ′ , at least one endpoint of that edge communicates over it (and thus initiates a message exchange) during the Δ𝑇 ℎ rounds. Indeed, by definition of a vertex cover, every edge in 𝐸 ′ has at least one endpoint in 𝑈 , and that endpoint communicates over that edge within the Δ𝑇 ℎ rounds. 3.2
□
Computing Sparse Subgraphs
Now, we describe our novel sparsification technique. The sparse subgraph that we obtain satisfies the below definition — see Definition 3.2. Definition 3.2. For any integers 𝜅, Δ𝑇 ℎ ⩾ 1, we define a 𝜅-detour, Δ𝑇 ℎ -threshold sparse subgraph 𝐺 ′ = (𝑉 , 𝐸 ′ ) of 𝐺 = (𝑉 , 𝐸) as follows. There exists some (distributedly known) superset 𝐻¯ of 𝐻 , where 𝐻 is the set of nodes with degree Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
15
¯ 𝑣 ∈ 𝐻¯ }, 𝐸𝐿 = 𝐸 \ 𝐸𝐻¯ , Ω(Δ𝑇 ℎ ) in 𝐺, such that if we let 𝐿 = 𝑉 \ 𝐻¯ denote the remaining nodes, 𝐸𝐻¯ = {{𝑢, 𝑣 } ∈ 𝐸 | 𝑢 ∈ 𝐻, 𝐸𝐻′¯ = 𝐸𝐻¯ ∩ 𝐸 ′ and 𝐸𝐿′ = 𝐸𝐿 ∩ 𝐸 ′ : (1) 𝐺 [𝐸𝐻′¯ ] and 𝐺 [𝐸𝐿′ ] maintain the connectivity of, respectively, 𝐺 [𝐸𝐻¯ ] and 𝐺 [𝐸𝐿 ],6 (2) 𝐺 [𝐸𝐻′¯ ] is a spanning forest that consists of trees 𝑇1, . . . ,𝑇𝑟 of diameter 𝐷 1, . . . , 𝐷𝑟 , such that
Í𝑟
𝑖=1 𝐷𝑖 = 𝑂 (𝜅),
(3) 𝐺 [𝐸𝐿′ ] has maximum degree 𝑂 (log 𝑛) and is a 𝑂 (log 𝑛) spanner (forest) of 𝐺 [𝐸𝐿 ].7 Note that if one separates the edge set 𝐸 of 𝐺 into 𝐸𝐻¯ and 𝐸𝐿 , then any shortest path in 𝐺 decomposes into a series of (alternating) shortest paths along 𝐺 [𝐸𝐻¯ ] and 𝐺 [𝐸𝐿 ] (or vice versa, depending on the shortest paths’ starting point). The natural next step is to sparsify 𝐸 — by sparsifying 𝐸𝐻¯ into 𝐸𝐻′¯ and 𝐸𝐿 into 𝐸𝐿′ , independently — into an edge set 𝐸 ′ = 𝐸𝐻′¯ ∪ 𝐸𝐿′ such that, for any shortest path in 𝐺, then its components along 𝐺 [𝐸𝐻¯ ] are stretched to a total of at most 𝑂 (𝑛 1−𝛿 log 𝑛) hops within 𝐺 [𝐸𝐻′¯ ], and its components along 𝐺 [𝐸𝐿 ] are stretched by 𝑂 (log 𝑛) hops within a low maximum degree subgraph. This latter condition, on the maximum degree, is crucial to our setting; it allows us to use 𝜅-detour, Δ𝑇 ℎ -threshold sparse subgraph subgraphs to obtain efficient rumor spreading algorithms in GOSSIP − CON GEST . Next, we describe a GOSSIP−CON GEST algorithm for computing a 𝑂 (𝑛 1−𝛿 log 𝑛)-detour, 𝑂 (𝑛𝛿 log 𝑛)-threshold sparse subgraph of 𝐺, for any known constant 0 ⩽ 𝛿 ⩽ 1. The algorithm takes 𝑂˜ (𝑛 1−𝛿 + 𝑛𝛿 ) = 𝑂˜ (𝑛 max(1−𝛿,𝛿 ) ) rounds, and consists of three types of phases: first a sampling phase, followed by several tree-merging phases, and finally, a sparsification phase. We describe these phases below. Sampling Phase. The algorithm starts with a sampling phase that consists of 𝑂 (𝑛𝛿 log 𝑛) rounds. Initially, all nodes choose to enter a star set 𝑆 with probability 𝑛 −𝛿 . Next, all non-star nodes enter either set 𝐻 or set 𝐿 — which stands for high degree and low degree sets respectively — depending on whether their degree is respectively greater than or equal to some threshold Θ(𝑛𝛿 log 𝑛), or lower than it. Then, each star node becomes the root of a cluster. After which, each non-star high degree node 𝑣 takes Θ(𝑛𝛿 log 𝑛) rounds to communicate over Θ(𝑛𝛿 log 𝑛) randomly chosen incident edges (with replacement). If in any such round, 𝑣 contacts (i.e., exchanges a message with) a star node, then after these Θ(𝑛𝛿 log 𝑛) rounds, 𝑣 joins the cluster rooted at that star node (and if there are multiple, 𝑣 chooses one such star neighbor arbitrarily). On the other hand, each low degree node 𝑢 takes Θ(𝑛𝛿 log 𝑛) rounds to communicate over all of its incident edges. This ensures that every node knows which incident edges lead to nodes in 𝐿. (In particular, all nodes in 𝐺 [𝐸𝐿 ] know which incident edges belong to that subgraph, and all other nodes learn that they have no such incident edges, i.e., that they are not in 𝐺 [𝐸𝐿 ].) Tree-Merging Phases. Subsequently, we run 𝑂 (log 𝑛) tree-merging phases on 𝐺 [𝑆 ∪ 𝐻 ]. (Note that 𝑆 ∪ 𝐻 corresponds to the 𝐻¯ for the sparse subgraph being computed.) Initially, the clusters are exactly the clusters formed of a star node and the high degree neighbors having joined that cluster. (Moreover, recall that each node knows, for each incident edge, whether the other endpoint is in 𝐿.) These phases are used to merge these clusters in a controlled manner until all nodes eventually belong to only one cluster. Each phase takes 𝑂 (𝑛 1−𝛿 log 𝑛) rounds. At the start, each cluster flips a coin to choose “heads” or “tails” with equal probability. If the coin was “tails”, the cluster then samples an outgoing edge in 𝐺 [𝑆 ∪ 𝐻 ] (see Section 2.3, where nodes 6 For clarity, for any 𝐹 ⊆ 𝐸 , the notation 𝐺 [𝐹 ] indicates the subgraph of 𝐺 whose edge set is 𝐹 , and whose vertex set consists of all of the endpoint
nodes of edges in 𝐹 . Note that this implies, here, that the vertex set of 𝐺 [𝐸𝐿 ] may contain nodes in 𝐻¯ , and that the vertex sets of 𝐺 [𝐸𝐻¯ ] and 𝐺 [𝐸𝐿 ] may intersect. 7 For any graph 𝐺 and stretch 𝑘 ⩾ 1, a 𝑘 -spanner 𝐺 ′ of 𝐺 is a subgraph of 𝐺 such that distances within 𝐺 ′ are at least as large as those in 𝐺 , but also at most a multiplicative factor 𝑘 higher. In other words, distances are stretched by at most a 𝑘 multiplicative factor. For a disconnected 𝐺 , we call 𝐺 ′ a 𝑘 -spanner forest if it defines a 𝑘 -spanner for each connected component of 𝐺 . Manuscript submitted to ACM
16
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
computes graph sketches only on edges with no endpoints in 𝐿), and otherwise the cluster waits for some incoming communication. Any sampled outgoing edge is kept only if the other endpoint’s cluster chose “heads”. Finally, the clusters connected together by the (kept) edges are merged together in a larger cluster. Note that the randomized process ensures that if we consider each larger cluster as a supergraph, where clusters are the nodes and two clusters are connected by an edge if there is some kept sampled edge between them, then the supergraph has diameter at most 2. After 𝑂 (log 𝑛) such tree-merging phases, every connected component of 𝐺 [𝑆 ∪ 𝐻 ] is spanned by a single tree, with diameter 𝑂 (𝑛 1−𝛿 log 𝑛), w.h.p. Then, each node in 𝐺 [𝑆 ∪ 𝐻 ] adds its incident edges within that spanning tree, to the edge set 𝐸𝐻′¯ ⊆ 𝐸 ′ of the output sparse subgraph. Sparsification Phase. Finally, we run a sparsification phase on 𝐺 [𝐸𝐿 ] = (𝑈 , 𝐸𝐿 ), where 𝐸𝐿 denotes all of the edges incident to any node in 𝐿. This sparsification phase takes 𝑂 (𝑛𝛿 log2 𝑛) rounds and it consists of the following steps. First, we run a GOSSIP − CON GEST simulation of the MPX algorithm [26] on 𝐺 [𝐸𝐿 ] using 𝑂 (𝑛𝛿 log2 𝑛) rounds — 𝐿 is a “low degree” vertex cover of 𝐺 [𝐸𝐿 ], thus we can use the simulation from Lemma 3.1. By simulating the MPX algorithm, we partition 𝑈 into clusters of diameter 𝑂 (log 𝑛) w.h.p., and such that for each node 𝑣 ∈ 𝑈 , the neighbors of 𝑣 are contained within at most 𝑂 (log 𝑛) clusters w.h.p. Subsequently, after the simulation of MPX is complete, each MPX cluster’s root broadcasts its ID to all of the cluster nodes in 𝑂 (log 𝑛) rounds (see Proposition 2.8 in Section 2.3). After which, nodes in 𝐿 simulate one round of CON GEST communication over 𝐺 [𝐸𝐿 ], using 𝑂 (𝑛𝛿 log2 𝑛) rounds, so that all nodes of 𝐺 [𝐸𝐿 ] learn the cluster’s ID of each of their neighbors (notice that for a given node, several of its neighbors might belong to the same cluster). Then, each node in 𝐺 [𝐸𝐿 ] keeps a single edge per neighboring cluster, and adds these edges to the edge set 𝐸𝐿′ ⊆ 𝐸 ′ of the output sparse subgraph. Analysis. We start by giving two lemmas for the sampling phase. Lemma 3.3. With high probability, it holds that: (1) There are at most 𝑂 (𝑛 1−𝛿 log 𝑛) star nodes, w.h.p. (2) Any high-degree node has a star neighbor, w.h.p. More precisely, any high-degree node 𝑣 has Θ(𝑑 (𝑣)𝑛 −𝛿 ) star neighbors w.h.p. Proof. Recall that each node becomes a star node with probability 𝑛 −𝛿 , independently and uniformly at random. Hence, out of all nodes, 𝑂 (𝑛 1−𝛿 ) become star nodes in expectation. By a simple application of the Chernoff bounds in Lemma 2.1, we see that 𝑂 (𝑛 1−𝛿 log 𝑛) nodes becomes stars w.h.p., thus proving the first item. As for the second item, note that any high degree node 𝑣, i.e., with degree 𝑑 (𝑣) = Ω(𝑛𝛿 log 𝑛), has in expectation 𝑑 (𝑣)𝑛 −𝛿 = Ω(log 𝑛) stars as neighbors. Once again, by a simple application of the Chernoff bounds in Lemma 2.1, we see that any high degree node has Θ(𝑑 (𝑣)𝑛 −𝛿 ) = Ω(log 𝑛) star neighbors w.h.p., thus proving the second item.
□
Lemma 3.4. Within the Θ(𝑛𝛿 log 𝑛) rounds of the sampling phase, any non-star high degree node chooses an edge leading to a star neighbor at least once, w.h.p. Proof. By Lemma 3.3, any non-star high degree node 𝑣 has Θ(𝑑 (𝑣)𝑛 −𝛿 ) star neighbors w.h.p. Now, in each round of the sampling phase, node 𝑣 contacts a neighbor chosen independently and uniformly at random. Hence, in each round node 𝑣 contacts a star neighbor with probability Θ(𝑑𝑑(𝑣)𝑛 (𝑣)
−𝛿 )
= Θ(𝑛 −𝛿 ). Hence, over Θ(𝑛𝛿 log 𝑛) rounds, 𝑣 contacts in
expectation Θ(log 𝑛) star neighbors. Finally, by a simple application of the Chernoff bounds in Lemma 2.1, we see that during the sampling phase, 𝑣 contacts at least one star neighbor w.h.p. Manuscript submitted to ACM
□
Fast Gossip-based Rumor Spreading using Small Messages
17
Next, we prove that the tree-merging phases indeed compute trees spanning each connected component of 𝐺 [𝑆 ∪ 𝐻 ], and whose diameter is linear in the number of (star) clusters present initially in the component. Lemma 3.5. Recall that 𝐸𝐻′¯ are the edges computed throughout the 𝑂 (log 𝑛) tree-merging phases. Overall, these treemerging phases take 𝑂 (𝑛 1−𝛿 log2 𝑛) rounds, and ensure that each connected component of 𝐺 [𝑆 ∪ 𝐻 ] induces a spanning tree in 𝐺 [𝐸𝐻′¯ ], of diameter 𝑂 (𝑋 ), where 𝑋 is the number of stars in that component. Proof. Consider any one connected component C of 𝐺 [𝑆 ∪ 𝐻 ], and let 𝑋 be the number of stars within that component. By Lemma 3.3, 𝑋 = 𝑂 (𝑛 1−𝛿 log 𝑛) w.h.p. Next, we show by induction that for any tree-merging phase 𝑖 ⩾ 0, the diameter of any cluster in C when the phase ends is at most min{2𝑖+1, 3𝑋 }. The base case is simple, since initially all clusters have diameter at most 2 (and if 𝑋 = 0, there are no clusters). Next, assume the induction hypothesis holds for some 𝑖 ⩾ 0. In phase 𝑖 + 1, the clusters’ diameter can grow by at most 2. (Otherwise, there exist two successive, directed inter-cluster edges along which we merge, but this contradicts the fact that we can merge only if an inter-cluster edge is from a tails cluster to a heads clusters.) Moreover, it is easy to see that for each cluster, there are at most 𝑋 stars contained within, and the stars are a dominating set on the cluster’s spanning tree. Hence, the diameter of any cluster in C is at most min{2𝑖+1, 3𝑋 }. This proves the induction step. Note that this inductive statement proves that each tree-merging phase can be executed in this model within 𝑂 (𝑛 1−𝛿 log 𝑛) rounds. Finally, we show for each tree-merging phase 𝑖 ⩾ 0, if we condition on the phase starting with some 𝑛𝑖 ⩾ 2 clusters, then the phase ends with at most 3𝑛𝑖 /4 clusters in expectation. First, note since all nodes know which incident edges lead to 𝐿, then all outgoing sampled edges are in 𝐺 [𝑆 ∪ 𝐻 ]. Thus, any cluster 𝐶 merges into another cluster if it flips tails, and looking at its outgoing edge, the cluster containing the other endpoint flipped heads. Hence, the probability that any other combination (of heads and tails for the two clusters) happens, which is at most 3/4, is an upper bound on the probability that 𝐶 does not merge with any cluster. The statement follows, and using the law of total expectation, we can show that if there are initially 𝑋 clusters in component C, then by the end of phase 𝑖 ⩾ 1, the expected number of clusters remaining is 𝑋 · (3/4)𝑖 ⩽ 𝑛 · (3/4)𝑖 . Finally, it suffices to use Markov’s inequality to show that after some 𝑂 (log 𝑛) tree-merging phases, taking altogether 𝑂 (𝑛 1−𝛿 log2 𝑛) rounds, a single cluster 𝐶 ∗ remains with high probability, and component C is spanned by the cluster tree of 𝐶 ∗ .
□
Finally, we show that the sparsification phase reduces the edge set of each connected component of 𝐺 [𝐸𝐿 ] down to a 𝑂 (log 𝑛) maximum degree, 𝑂 (log 𝑛) stretch spanner. Lemma 3.6. Recall that 𝐸𝐿′ are the edges computed in the sparsification phase. The sparsification phase takes 𝑂 (𝑛𝛿 log2 𝑛) rounds, and ensures that 𝐺 [𝐸𝐿′ ] has maximum degree 𝑂 (log 𝑛) and is a 𝑂 (log 𝑛)-spanner (forest) of 𝐺 [𝐸𝐿 ]. Proof. First, we point out that executing the MPX algorithm of [26] on some 𝑛-node graph 𝐺 = (𝑉 , 𝐸) takes 𝑂 (log 𝑛) rounds, and outputs a low diameter graph decomposition of 𝐺: that is, a partition of the vertex set 𝑉 into subsets 𝑉1, . . . , 𝑉𝑘 such that each cluster 𝑉𝑖 has strong diameter at most 𝑂 (log 𝑛) and is spanned by a tree of depth 𝑂 (log 𝑛). Since, by definition, 𝐿 is a vertex cover of 𝐸𝐿 and nodes in 𝐿 have at most 𝑂 (𝑛𝛿 log 𝑛) incident edges in 𝐺, then by Lemma 3.1, the 𝑂 (log 𝑛) rounds of the MPX algorithm on (the connected components of) 𝐺 [𝐸𝐿 ] can indeed be simulated by a 𝑂 (𝑛𝛿 log2 𝑛) round GOSSIP − CON GEST algorithm. After computing such a low diameter graph decomposition, broadcasting the ID of each cluster’s root over each cluster’s spanning tree takes 𝑂 (log 𝑛) rounds by Proposition 2.8. Then, by Lemma 3.1, a single round of communication over (the connected components of) 𝐺 [𝐸𝐿 ] can indeed be simulated by a 𝑂 (𝑛𝛿 log 𝑛) round GOSSIP − CON GEST Manuscript submitted to ACM
18
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
algorithm. At which point, each node in 𝐺 [𝐸𝐿 ] knows, for each incident edge 𝑒 ∈ 𝐸𝐿 , whether the other endpoint of edge 𝑒 lies in the same cluster. Thus, by the algorithm description, each node in 𝐺 [𝐸𝐿 ] adds one incident edge to 𝐸𝐿′ per neighboring cluster. Now, note that Corollary 3.9 of [23] proves that with high probability, each node 𝑣 ∈ 𝑉 neighbors 𝑂 (log 𝑛) clusters, or in other words, the neighbors of 𝑣 belong to at most 𝑂 (log 𝑛) clusters. Hence, each node in 𝐺 [𝐸𝐿 ] has maximum degree 𝑂 (log 𝑛) in 𝐺 [𝐸𝐿′ ]. As for the 𝑂 (log 𝑛) stretch, consider any shortest path from any two nodes 𝑢, 𝑣 within one connected component of 𝐺 [𝐸𝐿 ]. Then, any edge in that path is replaced in 𝐺 [𝐸𝐿′ ] by a path of at most 𝑂 (log 𝑛) hops that includes at most one inter-cluster edge, and 𝑂 (log 𝑛) edges within a cluster’s spanning tree.
□
Finally, we show that our sparsification technique indeed computes a 𝑂 (𝑛 1−𝛿 log 𝑛)-detour, 𝑂 (𝑛𝛿 log 𝑛)-threshold sparse subgraph of 𝐺. Theorem 3.7. For any constant 0 ⩽ 𝛿 ⩽ 1, there exists a GOSSIP − CON GEST algorithm that computes a 𝑂 (𝑛 1−𝛿 log 𝑛)-detour, 𝑂 (𝑛𝛿 log 𝑛)-threshold sparse subgraph of 𝐺, in 𝑂 (𝑛 max(1−𝛿,𝛿 ) log2 𝑛) rounds. Proof. Let 𝐻¯ = 𝑆 ∪ 𝐻 , then 𝐻¯ is a superset of 𝐻 , the nodes with degree at least Ω(𝑛𝛿 log 𝑛) in 𝐺. Moreover, by the algorithm description, 𝐺 ′ = (𝑉 , 𝐸 ′ ) where 𝐸 ′ = 𝐸𝐻¯ ′ ∪ 𝐸𝐿′ . Next, consider 𝐺 [𝐸𝐻′¯ ]. By Lemma 3.5, each connected component 𝐺 [𝐻¯ ] = 𝐺 [𝐸𝐻¯ ] induces a spanning tree in 𝐺 [𝐸 ′ ], thus maintains the connectivity of 𝐺 [𝐸𝐻¯ ]. Moreover, each 𝐻¯
such spanning tree𝑇𝑖 has diameter 𝐷𝑖 = 𝑂 (𝑋𝑖 ), where 𝑋𝑖 is the number of stars in𝑇𝑖 . Since there are at most 𝑂 (𝑛 1−𝛿 log 𝑛) Í star nodes w.h.p., by Lemma 3.3, then it follows that 𝑟𝑖=1 𝐷𝑖 = 𝑂 (𝑛 1−𝛿 log 𝑛). Finally, consider 𝐺 [𝐸𝐿′ ]. Then, by Lemma 3.6, 𝐺 [𝐸𝐿′ ] has maximum degree 𝑂 (log 𝑛) and is a 𝑂 (log 𝑛)-spanner (forest) of 𝐺 [𝐸𝐿 ]. In particular, this implies that 𝐺 [𝐸𝐿′ ] maintains the connectivity of 𝐺 [𝐸𝐿 ]. Hence, 𝐺 ′ is indeed a 𝑂 (𝑛 1−𝛿 log 𝑛)-detour, 𝑂 (𝑛𝛿 log 𝑛)-threshold sparse subgraph of 𝐺. Finally, the runtime for computing the sparse subgraph 𝐺 ′ is 𝑂 (𝑛𝛿 log 𝑛)+𝑂 (𝑛 1−𝛿 log2 𝑛)+𝑂 (𝑛𝛿 log2 𝑛) = 𝑂 (𝑛 max(1−𝛿,𝛿 ) log2 𝑛). □ 3.3
Rumor Spreading
√ √ We now describe our rumor spreading algorithm. We start by computing a 𝑂 ( 𝑛 log 𝑛)-detour, 𝑂 ( 𝑛 log 𝑛)-threshold √ sparse subgraph 𝐺 ′ = (𝑉 , 𝐸 ′ ) in 𝑂˜ ( 𝑛) rounds — see Theorem 3.7. Let 𝐻¯ denote the (distributedly known) node superset √ of the nodes with degree Ω( 𝑛 log 𝑛) in 𝐺, and 𝐸𝐻′¯ and 𝐸𝐿′ the two edge subsets of 𝐸 ′ as described in Definition 3.2. √ Next, all nodes participate in 𝑂 ((𝐷 + 𝑛) log 𝑛) multiple rumor spreading phases, each of which consists of 𝑂 (log 𝑛) rounds, and terminate. Each phase ensures that the rumor spreads by at least one hop along any shortest path in 𝐺 ′ . More precisely, during each phase, the first round consists of each node in 𝐻¯ contacting their parent within 𝐸 ′ — recall 𝐻
that 𝐺 [𝐸𝐻′¯ ] is a spanning forest — and both nodes exchange the rumor, if they have it, along that edge. The remainder of the phase’s rounds are used to simulate one round of CON GEST communication between the nodes in 𝐺 [𝐸𝐿′ ]. Note that such a round can indeed be simulated with a 𝑂 (log 𝑛) blow up in GOSSIP − CON GEST , since 𝐺 [𝐸𝐿′ ] has maximum degree 𝑂 (log 𝑛) — see Lemma 3.1. Theorem 1.2. There exists a GOSSIP − CON GEST algorithm solving rumor spreading, with high probability, in √ 𝑂˜ (𝐷 + 𝑛) rounds. √ √ Proof. By Theorem 3.7, computing a 𝑂 ( 𝑛 log 𝑛)-detour, 𝑂 ( 𝑛 log 𝑛)-threshold sparse subgraph 𝐺 ′ = (𝑉 , 𝐸 ′ ) takes √ 𝑂 ( 𝑛 log2 𝑛) rounds. Then, it remains to show that the rumor is spread, from some source node 𝑢 to all nodes in 𝐺 via √ 𝐺 ′ , in 𝑂˜ (𝐷 + 𝑛) rounds. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
19
Next, let 𝑢 be the source that initially holds the rumor. Then, by the algorithm description and the properties of 𝐺 ′ , we can show that the rumor spreads by one hop within 𝐺 ′ per phase. Indeed, the first round of a phase suffices to spread the rumor by one hop along 𝐺 [𝐸𝐻¯ ], since any node 𝑣 holding the rumor within 𝐺 [𝐸𝐻¯ ] lies in a tree (by definition of 𝐺 ′ ), contacts its parent and is contacted by its children, and thus by the algorithm description, exchanges the rumor with its parent and its children within that round. As for spreading the rumor by one hop along 𝐺 [𝐸𝐿′ ], note that 𝐺 [𝐸𝐿′ ] has maximum degree 𝑂 (log 𝑛), thus by Lemma 3.1, 𝑂 (log 𝑛) rounds of GOSSIP − CON GEST can simulate a single round of CON GEST communication in which each node within 𝐺 [𝐸𝐿′ ] with the rumor sends it to all of its neighbors (in 𝐺 [𝐸𝐿′ ]). To sum up, a rumor spreading phase succeeds in spreading the rumor by (at least) one hop along 𝐺 [𝐸 ′ ]. Finally, it remains to consider the stretch induced by 𝐺 ′ compared to 𝐺. On 𝐺 [𝐸𝐿 ], 𝐺 ′ induces a multiplicative, √ 𝑂 (log 𝑛) stretch. On 𝐺 [𝐸𝐻¯ ], 𝐺 ′ induces an additive, 𝑂 ( 𝑛 log 𝑛) stretch (over the sum of all spanning trees). Since the diameter 𝐷 upper bounds the distance from 𝑢 to any other node 𝑣 ∈ 𝑉 within 𝐺, we get that the rumor spreading in 𝐺 ′ √ √ succeeds in 𝑂 ((𝐷 + 𝑛) log 𝑛) rumor spreading phases, and thus in 𝑂 ((𝐷 + 𝑛) log2 𝑛) rounds. □ Removing Knowledge of 𝐷. Note that the rumor spreading algorithm’s description given above, and the obtained runtime, relies on all nodes knowing constant factor upper bounds on both the diameter 𝐷 and the number of nodes 𝑛. However, it suffices to know a constant factor upper bound on 𝑛 only, since we can estimate the diameter 𝐷 in an exponentially growing fashion. To do so, modify the above described rumor spreading algorithm by having nodes start with the same, but constant, √ estimate of 𝐷 — denoted by 𝐷𝑒𝑠𝑡 . Then, nodes run the above algorithm for 𝑂˜ (𝐷𝑒𝑠𝑡 + 𝑛) rounds, and keep track of which neighbor they first received the rumor from. This forms a tree, rooted in the node with the rumor, and the tree spans 𝐺 if and only if the rumor has spread to every node. This provides a simple condition with which nodes can detect whether the rumor spreading algorithm has terminated. We describe the detection mechanism. Every node that received the rumor, must be part of some tree. These nodes detect termination as follows. First, they aggregate information up the tree, so that the root can sample an outgoing edge w.h.p., if there exists one (see Section 2.3). Following which, the root executes a broadcast. Depending on whether the sampling procedure succeeds or not — where if the procedure fails, then this implies that there are no outgoing edges — the broadcast informs all nodes in the tree to, respectively, double their estimate 𝐷𝑒𝑠𝑡 or to terminate. Note that all nodes without the rumor, and by extension not within the tree, know that the estimate 𝐷𝑒𝑠𝑡 is incorrect and thus double it. Since all nodes know the same constant approximation of 𝑛 and the same estimate 𝐷𝑒𝑠𝑡 , they can wait until the correct round to start the next iteration of the algorithm with the new estimate.
4
Rumor Spreading in Graphs with Large Weak Conductance
Any graph with weak conductance Φ𝑐 , for some value of the parameter 𝑐 ⩾ 1, can be decomposed into at most ⌊𝑐⌋ pairwise kernel-disjoint sunflowers (see Lemma 2.2). Combining this structural property with graph sketching techniques, we solve rumor spreading (as well as spanning tree construction and leader election) while using only 𝑂 (polylog 𝑛)-sized messages. Moreover, we do so with a time complexity of 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds, which improves on that of [5] (where the latter requires messages with size linear in 𝑛). Note that as a result, we also show that for graphs with good weak conductance for small enough 𝑐 ⩾ 1, that is, such that 𝑐/𝜙𝑐 = 𝑂 (polylog 𝑛), we can obtain fast (i.e., 𝑂 (polylog 𝑛) rounds) and message-efficient (i.e., 𝑂˜ (𝑛) messages) spanning tree construction (and leader election) even in the GOSSIP − CON GEST model. Manuscript submitted to ACM
20
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
4.1
Super Cluster Primitives
Before presenting our rumor spreading algorithm for weak conductance graphs, we first give several more basic communication primitives. These primitives cope with the fact that we cannot afford to merge several clusters (and their spanning trees) into a single one for much of the algorithm presented in Section 4.2, otherwise its runtime would grow significantly. Hence, we define and leverage super clusters — these are collection of clusters with good communication properties in GOSSIP − CON GEST . More formally, a super cluster of size 𝑘 ⩾ 1 and depth 𝑇 is a triple containing (1) a set of some 𝑘 ⩾ 1 clusters, (2) a set of 𝑘 disjoint trees, each spanning one of the clusters and of diameter at most 𝑇 , and (3) a set of (undirected) inter-cluster edges. Moreover, the inter-cluster edges must satisfy the following properties. First, for each inter-cluster edge, at least one of the endpoints is responsible for communication (i.e., only this node is allowed to contact the other endpoint), and that endpoint node knows that it is responsible for that edge. Second, no two inter-cluster edges are incident, i.e., each node is responsible for the communication of a single incident edge. Next, we implement several basic distributed primitives for super clusters time-efficiently. To do so, we show how any super cluster can efficiently simulate a communication-restricted distributed algorithm on the following cluster supergraph: each cluster is a (super) node, and two clusters (or super nodes) are connected if some inter-cluster edge has its endpoints in both clusters. More concretely, we provide the simulation for synchronous distributed algorithms. Such algorithms proceed in iterations (to distinguish from the rounds used by the nodes in the original communication graph), and within each iteration, a super node (1) executes some local computation, where “local” here means 𝑂 (𝑇 )-round operations restricted to the cluster (e.g., broadcast, convergecast, etc.), (2) sends the same message to all its (super node) neighbors (i.e., broadcast communication), and (3) receives an aggregate (e.g., bitwise OR, average, sum, min, max, etc.) of the messages sent by its neighbors. Then, a single iteration on the supergraph can be simulated via 𝑂 (𝑇 ) rounds in the original communication graph, by leveraging the super cluster’s structure. That is, to simulate one iteration, first each cluster’s root computes what message it would send on the supergraph, and then the root broadcasts that message over its cluster, in 𝑂 (𝑇 ) rounds. Second, all inter-cluster edges are used to communicate; for any inter-cluster edge 𝑒 incident to any node 𝑣 in the cluster, if 𝑣 is responsible for communication over 𝑒, then 𝑣 contacts the other endpoint of 𝑒 after receiving the broadcast from its cluster root. (This takes a single round, since each node is responsible for at most one incident edge.) Third and finally, each cluster convergecasts, and in doing so, aggregates the information received by any of its nodes from other clusters. Proposition 4.1. Consider any 𝑛-node graph 𝐺, any super cluster of size 𝑘 and depth 𝑇 (where 𝑇 is some known upper bound) and any 𝑇𝐼 -iteration algorithm A designed in the above described model. Then, the super cluster simulates the execution of A on the cluster supergraph, in 𝑂 (𝑇 · 𝑇𝐼 ) rounds. With the above simulation, we can implement some basic primitives for Section 4. The first flooding primitive is quite straightforward. All clusters have their own inputs, either some IDs or some boolean, as well as an integer input 𝛽 ⩾ 1. Then, the primitive simulates a basic 𝛽 round flooding algorithm on the cluster supergraph. If the initial inputs are IDs (respectively, booleans), then in that supergraph, each node simply sends the highest ID (respectively, the OR of all booleans) seen until now to all of its neighbors, and upon aggregating any received IDs (respectively, booleans), keeps the maximum one (respectively, the OR result). Since the algorithm on the cluster supergraph trivially takes 𝑂 (𝛽) iterations, the primitive on 𝐺 takes 𝑂 (𝛽𝑇 ) rounds (by Proposition 4.1).
Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
21
Proposition 4.2. Consider any 𝑛-node graph 𝐺, and any super cluster of size 𝑘 and depth 𝑇 (where 𝑇 is some known upper bound). For any integer 𝛽 ⩾ 1, each cluster (root) can receive an aggregate of the values of all clusters within distance 𝛽 on the cluster supergraph, in 𝑂 (𝛽𝑇 ) rounds. This flooding primitive is a basic building block for the remaining primitives on super clusters. For example, given some integer input 𝛽 ⩾ 1, say we want to detect if the eccentricity of the cluster with maximum root ID, within the cluster supergraph, is at most 𝛽. (We use this problem as a simple and efficient alternative to the problem of detecting whether the diameter of the cluster supergraph is at most 𝛽.) This distributed detection problem can be defined as follows (on the cluster supergraph). If that eccentricity is most 𝛽, then the cluster with maximum root ID should output true whereas all other clusters should output false. Otherwise, all clusters should output false. This distributed detection problem can be solved easily, even within the restricted distributed model we consider for algorithms running on the cluster supergraph. More precisely, we first run the flooding primitive, using the cluster root IDs, for 𝛽 + 1 iterations. If any cluster sees its maximum highest ID seen until now change between the 𝛽th iteration and the last, (𝛽 + 1)th iteration, then that cluster detects the eccentricity in question is strictly higher than 𝛽. Next, we run the flooding primitive again, but for 𝛽 iterations and where the initial input of each cluster is a boolean — set to true if the cluster detected the above, and false otherwise. Finally, the output is decided as follows: any cluster (root) that did not see any higher ID during the first flooding primitive, nor received any true boolean value during the second flooding primitive, sets its output value to true. Proposition 4.3. Consider any 𝑛-node graph 𝐺, and any super cluster of size 𝑘 and depth 𝑇 (where 𝑇 is some known upper bound). For any integer 𝛽 ⩾ 1, the cluster with maximum root ID cluster can detect if its eccentricity in the cluster supergraph is strictly higher than 𝛽 or not, in 𝑂 (𝛽𝑇 ) rounds. Now, consider that the previous primitive returns that the eccentricity of the cluster with maximum root ID, within the cluster supergraph, is at most 𝛽, for some integer 𝛽 ⩾ 1. Then, we can time-efficiently merge all clusters into a single one in the GOSSIP − CON GEST model. More precisely, for all nodes in the super cluster, we modify its parent, if needed, such that the corresponding edges for a single spanning tree of diameter at most 𝛽𝑇 covering all of the super cluster’s nodes. To do this, it suffices to run the flooding primitive (with IDs) twice, where nodes learn during the first flooding the maximum root ID in the super cluster, and learn during the second flooding which node is their parent in the new tree (i.e., the node from which they receive the ID corresponding to the maximum root ID from the first flooding). Proposition 4.4. Consider some 𝑛-node graph 𝐺 and super cluster of size 𝑘 and depth 𝑇 (where 𝑇 is some known upper bound), and let 𝑈 denote the nodes in the super cluster. If the eccentricity of the cluster with maximum root ID is at most 𝛽, for some integer 𝛽 ⩾ 1, in the cluster supergraph, then we can construct a spanning tree of 𝑈 with diameter at most 2𝛽𝑇 , in 𝑂 (𝛽𝑇 ) rounds. Given such a spanning tree, we can time-efficiently (i.e., in 𝑂 (𝛽𝑇 ) rounds) compute an outgoing edge in GOSSIP − CON GEST — by directly using primitives from Section 2.3. (Where here, outgoing means an edge leading to some node not in the super cluster, if any exists.) Moreover, note that for any such super cluster (i.e., fulfilling the above eccentricity condition), we can compute a temporary spanning tree. Indeed, if we make sure that nodes keep in memory the previous edges, then as a result, after some fixed number of rounds known to all nodes (e.g., once we’ve sampled an outgoing edge of the super cluster), we can revert back to the original super cluster (i.e., with spanning tree for each cluster, and inter-cluster edges). Manuscript submitted to ACM
22
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
4.2
Algorithm
Consider some communication graph 𝐺 with weak conductance Φ𝑐 , for some value of the parameter 𝑐 ⩾ 1, and let 𝑇 (𝑛) = 𝑂 (log 𝑛/Φ𝑐 ) be an upper bound (whose only dependency on 𝑐 is captured by Φ𝑐 ) on the runtime of the primitives in Section 2.2 for a graph of 𝑛 nodes and weak conductance Φ𝑐 . Also, let 𝑐 ∗ = ⌊𝑐⌋. We give a spanning tree construction algorithm that takes 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds. We separate the algorithm into two parts: a set-up part and a tree-merging part. In the set-up part, we “compute” a decomposition of 𝐺 into at most 𝑐 ∗ pairwise kernel-disjoint sunflowers, but in a distributed fashion. More precisely, we compute a decomposition of 𝐺 into at most 𝑐 ∗ disjoint clusters — each corresponding to one such sunflower — such that each cluster is spanned by a tree of 𝑂 (log 𝑛/Φ𝑐 ) depth. A subtle point is that we do not compute the decomposition into sunflowers exactly; indeed, this would give us non-disjoint clusters whereas we need disjoint clusters for the next, tree-merging part. Instead, we carefully assign nodes in the intersection of the sunflowers (which are pairwise kernel-disjoint, but not pairwise disjoint) to a single cluster, without increasing the cluster’s diameter. After which, we take these clusters to be the initial clusters of the tree-merging part, which will combine the clusters’ spanning tree into a single tree spanning the whole graph 𝐺. To merge these clusters fast, we leverage graph sketching techniques. Moreover, we merge clusters in a slightly unusual way. Both techniques combined together lead to our 𝑂 (𝑐 log 𝑛/Φ𝑐 ) runtime.8 Set-up. In the set-up part, we run 𝑐 ∗ phases. Initially, all nodes are uncovered (i.e., 𝐶 0 = ∅), and at the end of each phase 𝑖, the covered nodes (denoted by 𝐶𝑖 ) form a (distributed) forest 𝐹𝑖 of at most 𝑐 ∗ (disjoint) trees, and of depth at most 2𝑇 (𝑛). (We remind that this means each node in a tree knows which edge leads to its parent, and additionally, we ensure each node knows its depth in the tree and the root’s ID.) Let 𝑈𝑖 = 𝑉 \ 𝐶𝑖 denote the uncovered nodes at the end of phase 𝑖. Each phase takes 6𝑇 (𝑛) rounds, and can be decomposed into the following three steps. In the first step, all nodes run (the modified, tree construction) uniform gossip for 2𝑇 (𝑛) rounds and construct a (distributed) forest 𝐹 ′ spanning the union of the sunflowers of nodes in 𝑈𝑖 −1 (see Corollary 2.7 in Section 2.3) — unless 𝑈𝑖 −1 = ∅, in which case no forest ends up being constructed. However, note that this forest may have depth 𝜔 (𝑇 ). In the second step, we prune the forest 𝐹 ′ . First, nodes run (modified, highest rumor) uniform spreading for 2𝑇 (𝑛) rounds, where each node’s initial rumor is the highest ID received during the first step. Any root of 𝐹 ′ that receives some higher ID becomes inactive for the remainder of this step; doing this will remove, from 𝐹 ′ , any tree that doesn’t span its root’s sunflower (whp). After which, for all active roots in 𝐹 ′ , we remove from their tree all nodes that are at depth strictly more than 2𝑇 (𝑛). To do so, all active roots in 𝐹 ′ (partial) broadcast simultaneously (see Section 2.3 for a description of the primitive) their ID over their tree, during the phase’s next 2𝑇 (𝑛) rounds. On the one hand, any node that receives any message over these 2𝑇 (𝑛) rounds now knows the root’s ID and can compute its depth within the tree (from the round in which it receives the message). In which case, we say it joins that tree. On the other hand, any node that did not receive a message (during these last 2𝑇 (𝑛) rounds) does not keep the edge to its parent computed in this phase’s first step, and as such does not join any tree in this phase. (Note that it may be part of some tree it joined in some previous phase.) Whenever a node joins a tree for the first time, it becomes covered. To summarize, the second step prunes forest 𝐹 ′ into some forest 𝐹 ′′ (rooted in the active nodes only), spanning less nodes, but with depth 2𝑇 (𝑛) and such that each tree spans its root’s sunflower.
8 Running most existing merging techniques for few, say 𝑜 (log 𝑛) phases, incurs a Ω (log∗ 𝑛) multiplicative overhead, if not Ω (log 𝑛) . Using such a
technique here would result in 𝜔 (𝑐 log 𝑛/Φ𝑐 ) runtime. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
23
In the third and final step, we merge the forest 𝐹𝑖 −1 obtained at the end of the previous phase, together with the forest 𝐹 ′′ computed in the current phase, by pruning away some unnecessary edges. More precisely, each node 𝑣 with multiple parents keeps the one with smallest depth (or more precisely, the one corresponding to the tree in which 𝑣 has smallest depth), and after that, the phase ends. Note that this third and last step ensures that the resulting forest 𝐹𝑖 has depth 𝑂 (log 𝑛/Φ𝑐 ), whereas a naive approach would lead to depth 𝑂 (𝑐 log 𝑛/Φ𝑐 ). Tree-Merging. After the set-up part, we have at most 𝑐 ∗ (disjoint) clusters such that each cluster is spanned by a tree of depth 2𝑇 (𝑛) = 𝑂 (log 𝑛/Φ𝑐 ). Progressively, we form larger sets of connected clusters, which we call super clusters. (Due to efficiency reasons, we maintain a loose structure for each super cluster — that is, we do not form a single tree spanning all nodes in the super cluster — until all phases of the merging are done. In what follows, we use primitives on super clusters described in Section 4.1.) More precisely, we run log 𝑐 ∗ phases, and each phase 𝑖 ensures that the (disjoint) super clusters each contain at least 2𝑖 clusters. After these log 𝑐 ∗ phases, a single super cluster contains all clusters, and it is straightforward to merge these together into a single spanning tree (see the primitive in Section 2.3) as well as use that tree to perform rumor spreading (via the broadcast and convergecast primitives from Section 2.3). Next, we describe how the super clusters merge in every phase, and how this is done in a way such that over all phases, only 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds suffice. Initially, each cluster is its own super cluster. Then, in phase 𝑖 ∈ {1, . . . , log 𝑐 ∗ }, each super cluster (roughly) checks if it contains at least 2𝑖 clusters, in which case it won’t merge in this phase. More precisely, if we define the cluster supergraph as the (virtual) graph in which each cluster is a (super) node, and two clusters (or super nodes) are connected if some inter-cluster edge has its endpoints in both clusters, then the super cluster performs the following simpler and more efficient procedure: it checks whether all clusters are within 2𝑖 distance, within the cluster supergraph, of the cluster with maximum root ID. If yes, then the super cluster samples an outgoing edge, and does so in 𝑂 (2𝑖𝑇 (𝑛)) rounds (where the constants hidden in 𝑂 do not depend on 𝑖, and for more details, see Propositions 4.4 and 2.9). Otherwise, the super cluster does nothing except possibly receive messages from other super clusters’ outgoing edges. (In this case, the super cluster simply waits for a phase that matches its number of clusters. While waiting, the super cluster may grow via the addition of some new clusters, which happens when clusters outside the super cluster find an outgoing edge leading to the super cluster.) 4.3
Analysis
We begin with several lemmas regarding the set-up part, and in particular we show Lemma 4.7. That is, after the set-up part, with high probability, we have decomposed 𝐺 into “few” disjoint clusters, and each has “small” diameter. Lemma 4.5. Consider any phase 𝑖 ∈ {0, . . . , 𝑐 ∗ } of the set-up part. Then, forest 𝐹𝑖 spans all covered nodes and has depth 2𝑇 (𝑛). Moreover, with high probability, it holds that: (1) For each root in 𝐹𝑖 , all nodes within its sunflower are covered. (2) For any two roots in 𝐹𝑖 , their sunflowers are pairwise kernel-disjoint. Proof. We prove the statement by induction on 𝑖. For the base case, note that no node is covered initially, and the forest is initially empty, hence the claim is trivially true. Next, we assume the induction hypothesis is true for some 𝑖 ∈ {0, . . . , 𝑐 ∗ − 1} and prove the induction step. (We prove that the induction step holds with high probability, and this coupled with a union bound over the 𝑐 ∗ ⩽ 𝑛 phases implies the lemma statement.) To do so, first note that the first two steps compute a forest 𝐹 ′ of depth 2𝑇 (𝑛) over the nodes that become covered in phase 𝑖 + 1. By Lemma 2.7, the first step constructs a forest. Then, the second step constructs 𝐹 ′′ by removing some Manuscript submitted to ACM
24
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
edge from 𝐹 ′ , thus 𝐹 ′′ is also a forest, and ensures that only nodes up to depth 2𝑇 (𝑛) in 𝐹 ′ are kept for 𝐹 ′′ . Indeed, only these nodes receive the partial broadcast message by Proposition 2.8. Finally, any node that becomes covered in phase 𝑖 + 1 is, by definition, spanned by 𝐹 ′′ . Next, note that the induction hypothesis for phase 𝑖 implies that any node covered in phase 𝑖 or earlier is part of 𝐹𝑖 , and that 𝐹𝑖 has depth at most 2𝑇 (𝑛). Now, recall that the algorithm description forces each covered node 𝑣 whose parent in 𝐹𝑖 differs from that in 𝐹 ′′ , to choose the one with smallest depth for 𝐹𝑖+1 (which 𝑣 deduces from its own depth in the corresponding forest). Let us assume by contradiction that we have a cycle in 𝐹𝑖+1 . However, by the above procedure, each node’s depth must be higher than that of its (possibly updated) parent. Since this cannot hold in a cycle, we get a contradiction and thus 𝐹𝑖+1 is a forest spanning the covered nodes at the end of phase 𝑖 + 1. Moreover, its depth is 2𝑇 (𝑛) because the depth of a node can only remain the same, or decrease, from 𝐹𝑖 ∪ 𝐹 ′′ to 𝐹𝑖+1 . We now show that the two items hold with high probability for 𝐹𝑖+1 . By the induction hypothesis for 𝑖, the two items respectively hold for any root and any two roots in 𝐹𝑖 . First, let us assume that the first item does not hold for any root in 𝐹 ′′ , say root 𝑟 . Then, it holds that some node 𝑣 in the sunflower of 𝑟 receives some higher ID (than that of 𝑟 ) from some other root node 𝑟 ′ of 𝐹 ′ during the first step (but 𝑣 does not join any tree in the second step). However, by Corollary 2.6, root 𝑟 receives this higher ID, or an even greater one, during the first 2𝑇 (𝑛) rounds of the second step with high probability. Thus, 𝑟 becomes inactive, which contradicts the fact that 𝑟 is a root of 𝐹 ′′ . As a result, we get that for any root in 𝐹 ′′ , and in fact, for any root in 𝐹𝑖+1 , all nodes within its sunflower are covered. Next, take any root 𝑟 in 𝐹 ′′ , and another root 𝑟 ′ from either 𝐹𝑖 or 𝐹 ′′ . Assume their sunflowers are not pairwise kernel-disjoint. If 𝑟 ′ is a root of 𝐹𝑖 , then by item 1 for 𝐹𝑖 , 𝑟 must be covered by the end of phase 𝑖, which leads to a contradiction with 𝑟 being a root of 𝐹 ′′ . Otherwise, if 𝑟 ′ is a root of 𝐹 ′′ , then by Corollary 2.6, the node with the smallest rumor among 𝑟 and 𝑟 ′ receives a rumor greater than its own during the first step, and thus does not become a root of 𝐹 ′ (and thus of 𝐹 ′′ also), which is also a contradiction. Hence, we get that the sunflowers of 𝑟 and 𝑟 ′ are pairwise kernel-disjoint with high probability, and thus the induction step holds with high probability. As mentioned above, this implies the lemma statement holds with high probability also.
□
Proposition 4.6. At the end of any phase 𝑖 ∈ {0, . . . , 𝑐 ∗ } of the set-up part, the number of uncovered nodes is at most 𝑛 − 𝑖 · 𝑛/𝑐, with high probability. Proof. By Lemma 4.5, the pairwise kernel-disjoint sunflowers of the forest’s roots (in phase 𝑖) contain only covered nodes, with high probability. By definition, these sunflowers each contain a unique set of at least 𝑛/𝑐 nodes (i.e., their kernel) and all these nodes are covered. Moreover, it is straightforward to see that at least one new root is added to the forest while there remains uncovered nodes. Hence, by the end of phase 𝑖, at most 𝑛 − 𝑖 · 𝑛/𝑐 nodes can remain uncovered, with high probability.
□
Lemma 4.7. Forest 𝐹𝑐 ∗ spans 𝐺, has depth 2𝑇 (𝑛) and contains at most 𝑐 ∗ trees, with high probability. Proof. By Lemma 4.5, forest 𝐹𝑐 ∗ has depth at most 2𝑇 (𝑛). By Proposition 4.6, it holds with high probability that the forest 𝐹𝑐 ∗ spans 𝐺. Moreover, it also holds with high probability that for any two roots in the forest, their sunflowers are pairwise kernel-disjoint. Since each such kernel contains at least 𝑛/𝑐 unique nodes, there can be at most 𝑐 roots in the forest. Since the number of roots is an integer, there are at most 𝑐 ∗ roots, and the statement follows.
□
Next, we show that each phase increases the number of clusters each super cluster must contain. This goes on until the end of phase log 𝑐 ∗ , when a single super cluster contains all up to 𝑐 ∗ clusters obtained from the set-up part. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
25
Lemma 4.8. Let 𝑘 be the number of initial clusters for the tree-merging phase. With high probability, it holds that when any (tree-merging) phase 𝑖 ∈ {0, . . . , log 𝑐 ∗ } ends, each super cluster contains at least min{2𝑖 , 𝑘} clusters. Proof. We prove the statement by induction on 𝑖. The base case for phase 𝑖 = 0 follows trivially, since all super clusters initially contain at least 1 cluster. Next, let us assume the induction hypothesis holds for some phase 0 ⩽ 𝑖 < log 𝑐 ∗ : i.e., each super cluster contains at least min{2𝑖 , 𝑘} clusters by the end of phase 𝑖. Then, we show that the induction step holds with high probability. (A union bound over the log 𝑐 ∗ ⩽ 𝑛 phases gives us the lemma statement.) Consider phase 𝑖 + 1. Super clusters cannot “lose” clusters (or put conversely, cluster do not “leave” super clusters), so any cluster that already has min{2𝑖+1, 𝑘} clusters when phase 𝑖 + 1 starts, still contains at least as many when phase 𝑖 + 1 ends. As for the other super clusters, containing at least min{2𝑖 , 𝑘} but strictly less than min{2𝑖+1, 𝑘} clusters, then for each super cluster, its cluster with maximum root ID is within distance at most min{2𝑖+1, 𝑘} to any other cluster, within the cluster supergraph. If 2𝑖+1 < 𝑘, then there exists at least one outgoing edge, and the super cluster samples one such outgoing edge with high probability. This outgoing edge leads to another super cluster with at least min{2𝑖 , 𝑘}, different clusters. This newly obtained super cluster (possibly resulting from the merging of many super clusters with min{2𝑖 , 𝑘} clusters) contains at least min{2𝑖+1, 𝑘} clusters, and the induction step follows (with some error probability polynomially small in 𝑛).
□
Finally, we can prove this section’s main result. Theorem 1.1. There exists a GOSSIP − CON GEST algorithm solving rumor spreading, with high probability, in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds with high probability, for every 𝑐 ⩾ 1 and where Φ𝑐 is the weak conductance of the graph. Proof. By Lemma 4.7, the tree-merging phase starts with at most 𝑘 ⩽ 𝑐 ∗ clusters with high probability, that altogether cover all nodes. Moreover, by Lemma 4.8, any super cluster must contain at least 𝑘 clusters by the end of tree-merging phase log 𝑐 ∗ . In other words, a single super cluster exists by the end of tree-merging phase log 𝑐 ∗ , and it covers graph 𝐺. After which, we construct a tree of diameter 𝑂 (𝑐 log 𝑛/Φ𝑐 ) spanning 𝐺 (see Proposition 4.4 from Section 2.3). Finally, convergecasting and broadcasting over this tree suffices to solve rumor spreading in another 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds. Let us now bound the round complexity. Each phase of the set-up part takes 𝑂 (log 𝑛/Φ𝑐 ) rounds, so over the 𝑐 ∗ phases, the set-up part takes 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds. As for the tree-merging part, each phase 𝑖 ∈ {1, . . . , log 𝑐 ∗ } takes 𝑂 (2𝑖𝑇 (𝑛)) ⩽ 𝛼2𝑖𝑇 (𝑛) rounds (for some constant 𝛼 > 0, independent of 𝑖). Summing up, we get that altogether, the Ílog 𝑐 ∗ phases take 𝑖=1 𝛼2𝑖𝑇 (𝑛) = 𝑂 (𝑐 ∗𝑇 (𝑛)) = 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds. Moreover, building a spanning tree of 𝐺 at the end of the merging part takes 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds by Proposition 4.4, and similarly for broadcast and convergecast over this spanning tree, by Proposition 2.8. Finally, it suffices to add up these round complexities. 5
□
Applications
We outline how our gossip algorithms can be used to solve other fundamental problems, such as computing aggregate functions, MST, and leader election. As mentioned earlier, both our gossip algorithms construct spanning trees over the graph as a byproduct, where the diameter of the spanning tree is upper bounded by the run time of the algorithm. Such a spanning tree can be constructed as follows: each node remembers the first edge along which it receives the rumor, and denotes the corresponding node as its parent in the tree. Manuscript submitted to ACM
26
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
On such spanning trees, leader election is trivial, as the root can be chosen as the leader and this information subsequently broadcasted to all nodes. Additionally, for functions where one may aggregate values, the root may learn the aggregate function over the entire graph in a single convergecast and subsequently spread this information to all nodes via a single broadcast. Thus, we see the following two sets of results. For graphs with weak conductance Φ𝑐 , we see that spanning tree construction, leader election, and (exact) aggregate function computation may be performed with high probability in 𝑂 (𝑐 log 𝑛/Φ𝑐 ) rounds. For general graphs, we see that spanning tree construction, leader election, and aggregate function computation √ may be performed with high probability in 𝑂˜ (𝐷 + 𝑛) rounds. √ Additionally, for general graphs, we can also construct an MST in 𝑂˜ (𝐷 + 𝑛) rounds. Recall that a byproduct of the √ algorithm for general graphs is a spanning tree of diameter 𝑂˜ (𝐷 + 𝑛). We can use this as a communication backbone, similar to the MST algorithm of Gmyr and Pandurangan [20]. In short, the MST construction is separated into two stages. Each stage is decomposed into Θ(log 𝑛) phases, each of which merges MST fragments. The first phase merges √ fragments up to a diameter of 𝑂 ( 𝑛) — any fragment with a higher diameter stops participating — using the fragments’ spanning trees for communication (i.e., to aggregate sketches at the root, so the root can sample a minimum-weight √ √ outgoing edge). At the end of the first stage, it holds that 𝑂 ( 𝑛) fragments remain, each of diameter 𝑂 ( 𝑛). The second stage proceeds through similar fragment-merging phases, in which the fragments are “virtually” merged (i.e., their fragment IDs are unified) while retaining their individual fragment spanning trees (as in [20]). However, at this stage, communication (to sample the minimum-weight outgoing edge by aggregating sketches of edges from the same fragments) is performed over the communication backbone. Both stages can be implemented gossip-efficiently, and √ thus, an MST is constructed in 𝑂˜ (𝐷 + 𝑛) rounds.
6
Conclusion
We presented the first-known gossip-based rumor spreading algorithm that uses small-sized messages and achieves a run time that depends on the weak conductance of the graph. Our algorithm is at least as good as the standard uniform gossip algorithm and, in many graphs, can be significantly (even exponentially, e.g., on dumbbell graphs) faster. Our algorithm improves on that of [4, 5], which used large message sizes and was also slower. Our algorithm’s performance bound in terms of weak conductance is essentially asymptotically optimal. We also presented a gossip-based rumor spreading algorithm that uses small-sized messages whose run time is independent of conductance (or weak conductance) and depends on the diameter of the graph. Our algorithm improves upon the previous best-known algorithm of [14], which also uses small messages. √ The most important open question is whether we can reduce our gossip time bound of 𝑂˜ (𝐷 + 𝑛) for rumor spreading √ in general graphs. We conjecture that this bound is essentially tight, i.e., Ω̃(𝐷 + 𝑛) is a round lower bound for gossip-based √ rumor spreading. We note that our algorithm can also be used to construct an MST in 𝑂˜ (𝐷 + 𝑛) gossip rounds, which is √ the optimal bound (up to logarithmic factors) one can obtain in terms of 𝐷 and 𝑛, since Ω̃(𝐷 + 𝑛) is a well-established lower bound for MST even in the standard (non-gossip) CON GEST model [29, 31].
Acknowledgments Gopal Pandurangan was supported in part by Army Research Office (ARO) grant W911NF-231-0191 and National Science Foundation (NSF) grant CCF-2402837. Manuscript submitted to ACM
Fast Gossip-based Rumor Spreading using Small Messages
27
References [1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459–467. [2] Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. 2012. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 961–970. [3] Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. 2017. Rumor Spreading with No Dependence on Conductance. SIAM J. Comput. 46, 1 (2017), 58–79. doi:10.1137/14099992X [4] Keren Censor-Hillel and Hadas Shachnai. 2011. Fast Information Spreading in Graphs with Large Weak Conductance. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 440–448. [5] Keren Censor-Hillel and Hadas Shachnai. 2012. Fast Information Spreading in Graphs with Large Weak Conductance. SIAM J. Comput. 41, 6 (2012), 1451–1465. doi:10.1137/110845380 [6] Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi. 2018. Rumor spreading and conductance. Journal of the ACM (JACM) 65, 4 (2018), 1–21. [7] Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Almost tight bounds for rumour spreading with conductance. In Proceedings of the forty-second ACM symposium on Theory of computing. 399–408. [8] Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Rumour spreading and graph conductance. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1657–1663. [9] Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2011. Rumor spreading in social networks. Theoretical Computer Science 412, 24 (2011), 2602–2610. [10] Robert Elsässer. 2006. On the communication complexity of randomized broadcasting in random-like graphs. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures. 148–157. [11] Paul Erdös and Richard Rado. 1960. Intersection Theorems for Systems of Sets. Journal of the London Mathematical Society s1-35, 1 (1960), 85–90. doi:10.1112/jlms/s1-35.1.85 [12] Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. 1990. Randomized broadcast in networks. Random Structures & Algorithms 1, 4 (1990), 447–460. [13] Alan M. Frieze and Geoffrey R. Grimmett. 1985. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics 10, 1 (1985), 57–77. [14] Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and broadcast with fewer messages, and faster gossiping. In 32nd International Symposium on Distributed Computing (DISC 2018), Vol. 121. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 30–1. [15] George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). 57–68. [16] George Giakkoupis, Frederik Mallmann-Trenn, and Hayk Saribekyan. 2019. How to Spread a Rumor: Call Your Neighbors or Take a Walk?. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, Peter Robinson and Faith Ellen (Eds.). ACM, 24–33. doi:10.1145/3293611.3331622 [17] George Giakkoupis and Thomas Sauerwald. 2012. Rumor spreading and vertex expansion. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, Yuval Rabani (Ed.). SIAM, 1623–1641. doi:10.1137/1.9781611973099. 129 [18] George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. 2014. Randomized rumor spreading in dynamic graphs. In International Colloquium on Automata, Languages, and Programming. Springer, 495–507. [19] George Giakkoupis and Philipp Woelfel. 2011. On the Randomness Requirements of Rumor Spreading. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, Dana Randall (Ed.). SIAM, 449–461. doi:10.1137/1.9781611973082.36 [20] Robert Gmyr and Gopal Pandurangan. 2018. Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 32–1. [21] Bernhard Haeupler. 2013. Simple, fast and deterministic gossip and rumor spreading. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. 705–716. [22] Bernhard Haeupler. 2015. Simple, fast and deterministic gossip and rumor spreading. Journal of the ACM (JACM) 62, 6 (2015), 1–18. [23] Bernhard Haeupler and David Wajc. 2016. A Faster Distributed Radio Broadcast Primitive: Extended Abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Chicago, Illinois, USA) (PODC ’16). Association for Computing Machinery, New York, NY, USA, 361–370. doi:10.1145/2933057.2933121 [24] Hossein Jowhari, Mert Saglam, and Gábor Tardos. 2011. Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, Maurizio Lenzerini and Thomas Schwentick (Eds.). ACM, 49–58. doi:10.1145/1989284.1989289 [25] Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. 2000. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 565–574. Manuscript submitted to ACM
28
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan
[26] Gary L. Miller, Richard Peng, and Shen Chen Xu. 2013. Parallel Graph Decompositions Using Random Shifts. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Montréal, Québec, Canada) (SPAA ’13). Association for Computing Machinery, New York, NY, USA, 196–203. doi:10.1145/2486159.2486180 [27] Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press. [28] Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2018. Fast distributed algorithms for connectivity and MST in large graphs. ACM Transactions on Parallel Computing (TOPC) 5, 1 (2018), 1–22. [29] David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput. 30, 5 (2000), 1427–1442. [30] Boris Pittel. 1987. On spreading a rumor. SIAM J. Appl. Math. 47, 1 (1987), 213–223. [31] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41, 5 (2012), 1235–1265.
Manuscript submitted to ACM