Broadcast in Almost Mixing Time

The CONGEST model is defined as follows. The network is modeled as a graph with $n$ nodes, where execution progresses in synchronous rounds. In each round, a node can send a message of size $O(\log n)$ bits to each of its neighbors. Importantly, nodes do not have prior knowledge of the network topology.

Although the CONGEST model has been extensively studied over the past two decades, the fundamental problem of broadcasting multiple messages remains unsolved for general topologies.

As pointed out by Ghaffari [21], the problem suggests an $\mathrm{\Omega }(D+k)$ round complexity lower bound, where $D$ is the diameter of the graph. For example, consider a path graph with $s$ as its first node. Any algorithm would require at least $D+k-1$ rounds to transmit all messages to the last node. However, this bound is only existential, meaning there exists a graph for which $\mathrm{\Omega }(D+k)$ rounds are needed. In contrast, consider a complete graph with $k=n$. Here, broadcasting can be completed in two rounds: in the first round, $s$ sends the $i$-th message to the node $i$, and in the second round, each node broadcasts the message it received in round $1$. This is significantly better than the $\mathrm{\Omega }(k)=\mathrm{\Omega }(n)$ bound suggested by the path graph example. These contrasting cases highlight the importance of algorithms that adapt to the underlying topology. Our paper presents such an algorithm, achieving universal optimality [20] on expander graphs. Specifically, it completes the multi-message broadcast on every expander $G$ in a number of rounds within a small overhead of the best possible for $G$. Before stating our results formally, we introduce some necessary terminology.

Throughout the paper, for a graph $G$, $E(G)$ is the edge set, $V(G)$ is the vertex set, $D(G)$ is the diameter, $d_G(v)$ is the degree of a node $v$ in $G$, $\delta (G)$ is the smallest vertex degree, and $\mathrm{\Delta }(G)$ is the largest vertex degree. We do not explicitly specify $G$ if it is obvious from the context, e.g., we can write $\delta$ instead of $\delta (G)$. With high probability (w.h.p.) means with a probability of at least $1-O(\frac{1}{n^C})$ for some constant $C>0$, with the probability being taken over both the randomness of the graph (when we assume random graphs) and the random bits of the algorithm. We assume that $\tilde{O}$ and $\tilde{\mathrm{\Omega }}$ hide $polylog(k,n)$ factors.

In multiple places in this paper, we are using classical Chernoff bounds.

One of the key graph-theoretical components in our approach is tree packing. A tree packing of a graph $G$ is a collection of spanning subtrees of $G$. The tree packing is characterized by three parameters: (1) its size $S$, i.e., the number of trees, (2) its diameter $H$, i.e., the maximal diameter of a tree, and (3) its weight $W$, i.e., the maximal number of trees sharing a single edge.

The present work focuses specifically on two graph families, namely Erdős–Rényi graphs and expanders. An Erdős–Rényi graph $G(n,p)$ is a graph on $n$ vertices where each edge exists independently from others with probability $p$ [16]. Throughout the paper, let $C_p$ denote a sufficiently large constant¹¹1It suffices to take $C_p=2700$. It was not a concern for the present work to optimize this constant. such that $G(n,p)$ is connected w.h.p. for $p\ge \frac{C_p\log n}{n}$. The condition $p=\mathrm{\Omega }(\frac{\log n}{n})$ is necessary, since for $p\le \frac{\log n}{n}$, there is a constant probability that the graph is disconnected [16].

We refer to a graph as an expander if it has small (polylogarithmic) mixing time²²2An alternative way is to say that expander graphs are those that feature an inverse polylogarithmic conductance; these two notions are equivalent..

For our purposes, it will be convenient to define the mixing time of an undirected graph by reconsidering it as being bidirected, that is, with each undirected edge $(u,v)$ replaced with $(u,v)$ and $(v,u)$. The mixing time ${\tau }_{mix}$ of a bidirected graph is defined as follows. Consider a lazy random process that starts at an arbitrary edge of the graph. At each step, with probability $\frac{1}{2}$, the process remains at the current edge, and with probability $\frac{1}{2}$, it transitions to a uniformly random adjacent edge (a directed edge $e_2$ is adjacent to a directed edge $e_1$ if they are of the form $e_1=(u,v)$ and $e_2=(v,w)$). It is known that this process admits a stationary distribution $\pi$, which is uniform over all edges. Moreover, regardless of the starting edge, the distribution $D_t$ of the walk after $t$ steps converges to $\pi$. We define ${\tau }_{mix}$ as the smallest $t$ for which $D_t$ is inversely polynomial close to $\pi$. For a formal definition, please refer to the full version of the paper [42]. We are now ready to formally state our results.

Our main result is an algorithm to solve the multi-message broadcast problem with only an overhead of $\tilde{O}({\tau }_{mix})$. We highlight that our algorithm can be run on any graph, but it will only be efficient on graphs with small ${\tau }_{mix}$, i.e., expanders.

In the analysis, we use $k/\delta (G)$ as a natural lower bound for $\mathrm{OPT}$. Indeed, if a node has degree $\delta (G)$, it requires at least $k/\delta (G)$ rounds to receive all $k$ messages. While this bound is meaningful on expander graphs, we show in Section 5.2 that it can be far from tight even on graphs with constant diameter, which highlights the necessity of exploiting expansion properties in our approach.

We design the algorithm for an arbitrary expander by building on the algorithm for random graphs, which achieves near-optimal performance in an important special case when the network is modeled as an Erdős–Rényi graph $G(n,p)$.

To obtain Theorem 4, we use the following result of independent interest, which contributes to a line of work [24, 11, 21, 7, 19] on low-diameter tree packing:

We construct the latter algorithm by utilizing multiple Coalescing Branching Random Walks [12] that run in parallel. To the best of our knowledge, this technique has never been used before in the context of distributed algorithms.

Finally, to map the terrain of the problem, we prove the hardness result in the centralized setting. Namely, we show that computing the exact number of rounds required for multi-message broadcast is NP-hard on general graphs.

In this section, we describe how to embed a random graph atop a given expander. A related technique was used by Ghaffari et al. [25], where it suffices to embed a sparse Erdős–Rényi graph with expected degree $O(\log n)$. In our setting, however, it is crucial to preserve the minimum degree of the host graph. To this end, we reuse Lemma 7 from [25], but we also introduce additional ideas of node groups and rejection sampling to meet our stronger requirements.

Embedding a graph $G$ atop a host graph $H$ involves creating virtual nodes $V(G)$ and establishing edges $E(G)$ between them so that

• $\mathrm{■}$

  Every virtual node $u\in V(G)$ is simulated by some physical node $\mathrm{host}(u)\in V(H)$.

• $\mathrm{■}$

  If a virtual node $u\in V(G)$ sends a message to $v\in V(G)$ along the edge $(u,v)\in E(G)$, this should be simulated by $\mathrm{host}(u)$ sending the same message to $\mathrm{host}(v)$ via some path in $H$.

Our construction will guarantee that each round of communication in $G$ can be simulated in $O({\tau }_{mix}(H)\cdot \log n)$ rounds in $H$ and that $\delta (G)$ will be close to $\delta (H)$. This gives us the following “lifting”: if there is an algorithm that solves a problem in $f(k,\log (|V(G)|),\delta (G))$ rounds on $G$ for some function $f$, then there is an algorithm that solves a problem in essentially $f(k,\log n,\delta (H))\cdot {\tau }_{mix}(H)\cdot \log n$ rounds on $H$. Formally,

This round complexity consists of three terms: $O((\frac{k}{\delta (H)}\cdot \log n+{\log }^{2}n)\cdot {\tau }_{mix}\cdot \log n)$ for simulating an algorithm, $O({\tau }_{mix}(H)\cdot {\log }^{2}n)$ rounds for constructing an embedding of an Erdős–Rényi graph knowing ${\tau }_{mix}(H)$, and $O({\tau }_{mix}(H)\cdot {\log }^{2}n)$ for estimating the ${\tau }_{mix}(H)$. Below, we describe the embedding and estimation parts.

We now overview the main primitive for our algorithm for an Erdős–Rényi graph – the COalescing-BRAnching Random Walk (COBRA walk). COBRA walk was first introduced by Dutta et al. [13] in their work “Coalescing-Branching Random Walks on Graph” [13], with subsequent refinements presented in [12, 38, 5]. The COBRA walk is a generalization of the classical random walk, defined as follows: At round $0$, a source node $s\in V$ possesses a token. At round $r$, each node possessing a token selects $\kappa$ of its neighbors uniformly at random, sends a token copy to each of them, and these neighbors are said to possess a token at round $r+1$. Here, $\kappa$, referred to as the branching factor, can be generalized to any positive real number [12]. When $\kappa =1$, the COBRA walk reduces to the classical random walk. From now on, we consider $\kappa$ to always be $2$. It is important to note that if a node receives multiple token copies in a round, it behaves as if it has received only one token; it will still choose $\kappa$ neighbors uniformly at random. This property, where received token copies coalesce at a node, gives the primitive its name.

Cooper et al. [12] studied the cover time of the COBRA walk on regular expanders and obtained the following theorem, which we use in our result

We point out that in [12], the bound on probability is $1-O(\frac{1}{n})$, though the analysis, which is based on Chernoff bounds, can be adapted so that the probability is $1-O(n^C)$ for any constant $C$ and the cover time is only multiplied by a constant.

In the upcoming analysis of our result, we will make sure that ${\lambda }_2$ is no more than $\frac{13}{14}$ w.h.p. Let $C_T$ be a sufficiently large constant so that a COBRA walk covers a regular graph with ${\lambda }_2\le \frac{13}{14}$ with probability at least $1-O(\frac{1}{n^2})$ in $C_T\cdot \log n$ rounds. From now on, we define $T$ to be $C_T\log n$.

The algorithm to solve the multi-message broadcast on an Erdős–Rényi graph $G(n,p)$ proceeds through the following steps:

1. 1.

   Building a BFS Tree and Gathering Information: Nodes construct a BFS tree rooted at the source node $s$. Using the tree, every node learns the total number of nodes $|V|$, the minimum degree $\delta$, and the maximum degree $\mathrm{\Delta }$. This step takes $O(D)$ rounds and does not require any prior knowledge of the graph topology.

2. 2.

   Regularizing the Graph: Each node $v$ adds $\mathrm{\Delta }-\text{deg}(v)$ self-loops to its adjacency list to make the graph regular. In our analysis, we will show that each node adds a relatively small number of self-loops. This operation is purely local and requires no communication between nodes.

3. 3.

   Constructing Spanning Subgraphs through Multiple COBRA Walks: The source node $s$ initiates $\delta$ COBRA walks by creating $\delta$ tokens labeled $1$ through $\delta$. When a token from the $i$-th COBRA walk is sent along an edge $e:(u,v)$, nodes $u$ and $v$ mark $e$ as part of the $i$-th subgraph. Note that a single edge may belong to multiple subgraphs.

   When running multiple COBRA walks simultaneously, congestion can occur if a node attempts to send multiple tokens from different COBRA walks along the same edge in a single round. Since only one token can traverse an edge per round, this creates a bottleneck that needs to be managed. To address this, we organize the process into phases, where each phase consists of $2$ rounds. In each phase, spanning rounds $\{2r,2r+1\}$, every node $u$ distributes two tokens for each COBRA walk whose token(s) it received during the previous phase. Since there are $\delta$ COBRA walks, node $u$ could have received at most $p\le \delta$ distinct tokens. Let these tokens be denoted by $t_1,\mathrm{\dots },t_p$. Node $u$ then distributes each token twice, as follows: it enumerates its neighbors as $v_1,\mathrm{\dots },v_{\mathrm{\ell }}$, with $\mathrm{\ell }\ge \delta$, generates two independent random permutations ${\sigma }_1,{\sigma }_2\in S_{\mathrm{\ell }}$, and sends token $t_i$ to neighbor $v_{{\sigma }_1(i)}$ in round $2r$ and to neighbor $v_{{\sigma }_2(i)}$ in round $2r+1$. Consequently, for any fixed COBRA walk $i$ and any node $u$, the token belonging to the $i$-th COBRA walk is sent to a neighbor of $u$ chosen uniformly at random, independently of the other tokens in that same COBRA walk. (Different cobra walks, however, need not be independent.)

   This step completes in $T$ phases.

   Parallel execution.

   For the rest of the algorithm, we run protocols on all the constructed subgraphs in parallel. To achieve this despite potential congestion (recall that each edge may belong to multiple subgraphs), we again organize the execution into phases. Now, each phase spans $2T$ rounds, ensuring that messages sent along any shared edge are distributed across the protocols without conflict. Specifically, if a protocol would send a message along an edge in a particular round when executed independently, all such messages from different subgraphs are scheduled within the same phase. This phased execution allows all protocols to proceed in parallel while respecting the edge capacity.

4. 4.

   Constructing Tree Packings: The source $s$ initiates a BFS on each subgraph to transform it into a tree. By the end of this step, the algorithm constructs a tree packing ${\{T_i\}}_{i\in [\delta ]}$. This step takes the number of phases that is at most the maximal eccentricity of $s$ among all the subgraphs, that is at most $O(T)$ phases, and hence $2T\cdot O(T)=O(T^2)$ rounds.

5. 5.

   Distributing Messages: The source node $s$ evenly divides the set of messages $M$ across the $\delta$ trees, ensuring that each tree receives $\frac{k}{\delta }$ messages. These messages are then downcasted along the trees one by one. To broadcast $\frac{k}{\delta }$ messages in a single tree of diameter $O(T)$ one needs $O(\frac{k}{\delta }+T)$ rounds. Hence, doing it in parallel in all trees takes $O(T\cdot (\frac{k}{\delta }+T))$ rounds.

The proof proceeds in three main steps. First, we argue that making a random graph regular by adding self-loops does not significantly affect its expansion properties. To this end, we rely on a result of Hoffman et al. [32], which shows that a random graph is a good expander with high probability. We also use standard Chernoff bound arguments to establish that random graphs are nearly regular, meaning the ratio between maximum and minimum degrees is close to one. Finally, we invoke a classical consequence of Weyl’s inequality, which ensures that small perturbations to the diagonal of a matrix only slightly affect its eigenvalues. Together, these ingredients imply that regularizing the graph preserves its spectral expansion up to a small error. We discuss the details at the end of this section, namely in subsection 4.4.

Assuming the expansion properties remain, the second step is to prove that each individual COBRA walk successfully covers the entire network. The permutation trick allows us to claim that, though COBRA walks are not independent, their marginal distributions stay as if they were. Using this, Theorem 10 by Cooper et al., together with a union bound, guarantees that all COBRA walks cover the whole graph within $O(\log n)$ phases w.h.p.

In the final step, we argue that the algorithm produces a tree packing with size $\delta (G)$, diameter $O(\log n)$, and weight $O(\log n)$. This tree packing allows for broadcasting all messages in $O({\log }^{2}n+\log n\cdot \frac{k}{\delta (G)})$ rounds. This is optimal up to additive ${\log }^{2}n$ and multiplicative $\log n$, as $\frac{k}{\delta (G)}$ provides a natural lower bound for the optimal broadcast time: if there is a node with degree $\delta$, it needs at least $k/\delta$ rounds to receive $k$ messages.

We now give the detailed proof starting from step 2, assuming step 1.

In this section, we demonstrate that multiple COBRA walks cover the graph fast, provided that it retains its expansion properties after adding self-loops. Formally, we assume the following lemma, which we prove in section 4.4.

Now, to see why multiple COBRAs do not congest, let us recall the permutation trick used in the algorithm. To be able to run multiple COBRA walks in parallel, we partition the execution into phases, each lasting $2$ rounds. In each phase, spanning rounds $2r,2r+1$, every node $u$ distributes two tokens for each COBRA walk whose token(s) it received during the previous phase. Since there are $\delta$ COBRA walks, node $u$ could have received at most $p\le \delta$ distinct tokens. Let these tokens be denoted by $t_1,\mathrm{\dots },t_p$. Node $u$ then distributes each token twice, as follows: it enumerates its neighbors as $v_1,\mathrm{\dots },v_{\mathrm{\ell }}$, with $\mathrm{\ell }\ge \delta$, generates two independent random permutations ${\sigma }_1,{\sigma }_2\in S_{\mathrm{\ell }}$, and sends token $t_i$ to neighbor $v_{{\sigma }_1(i)}$ in round $2r$ and to neighbor $v_{{\sigma }_2(i)}$ in round $2r+1$.

The claim below summarizes the properties resulting from the procedure described:

To conclude the analysis of multi-COBRA’s performance on a random graph, we combine Lemma 11 and Claim 12 and get the following lemma.

In this section, we show how to obtain a tree packing from multi-COBRA’s edge assignment and describe how we use this tree packing to broadcast the messages.

The following two lemmas speak about the properties of the spanning graphs obtained via multi-COBRA.

In this Section, we prove Lemma 11 that states that graph’s expansion properties are preserved after adding self-loops. We start by providing relevant concepts from spectral theory.

The following Lemma shows that with high probability, an Erdős–Rényi graph $G(n,p)$ is almost regular.

We prove that determining the optimal number of rounds for the multi-message broadcast problem in CONGEST is NP-hard in the centralized setting. To do that, we reduce the Set splitting problem to the multi-message broadcast.

In our reduction, for simplicity of presentation, we allow edges to have arbitrary bandwidth instead of $\tilde{O}(1)$, since, as we show, this can be simulated in CONGEST. In the reduction, the initial set $S$ corresponds to the set $M$ of messages, and $s$ has two dedicated children to which it can send $n_1$ and $n_2$ messages, respectively with $n_1+n_2=k$, simulating the splitting. Deciding how to split messages between these two children is the only “smart” choice an algorithm should make; all other nodes are just forwarding messages they receive. For the full version of the proof, please see the full version of the paper [42].

It is tempting to argue for an approximation factor of an algorithm by comparing its round complexity to two straightforward lower bounds: $D(G)$ and $\frac{k}{\text{minCut}(G)}$. Unfortunately, those are not sufficient as there is an instance (see Figure 2) where $D(G)=O(1)$ and $\frac{k}{minCut(G)}=O(1)$, but the optimal answer is $\mathrm{\Omega }(\sqrt{k})$. As for NP-hardness, we consider a more general model where edges might have arbitrary bandwidth, but we show that this can be simulated in CONGEST.

To transform a graph with arbitrary bandwidths to a graph with all bandwidths equal to $1$, we do the following. The source $s$ corresponds to a single node in the new graph. For a node $v\ne s$ in the original graph, let $B$ denote the maximal bandwidth of its adjacent edges. In the new graph, node $v$ then corresponds to a clique of $B$ nodes. We call this clique a $v$-clique. If in the original graph nodes $v\ne s$ and $u\ne s$ were connected by an edge of bandwidth $b$, we pick (arbitrary) $b$ nodes in $v$-clique, $b$ nodes in $u$-clique, and draw $b$ edges between picked nodes to establish a perfect matching. For every edge $(s,u)$ of bandwidth $b$, we connect the new source with $b$ arbitrary nodes of the $u$-clique. We call the resulting graph the corresponding CONGEST graph.