Distributed Branching Random Walks and Their Applications

Let $G=(V,E)$ be a connected graph that denotes a network of nodes, where $V$ and $E$ are the set of nodes and set of (bidirectional) communication links, respectively. As is typical, $|V|=n$ and $|E|=m$. The nodes in the graph represent a fixed set of computing entities, where each node is associated with a unique identifier (or id). Moreover, we assume that the id of any node can be encoded in $O(\log n)$ bits.

The system proceeds in synchronous rounds, i.e., a message $m$ sent by a node $u$ in any round is received by its recipient node $v$ by the end of that round.

Let $d(u)=|N(u)|$ and $d(S)={\sum }_{u\in S}d(u)$ be the degree of node $u$ and volume of subset $S\subseteq V$ (resp.), where $N(u)=\{v\mid (u,v)\in E\}$ is the set of neighbors of node $u$. Let $\mathrm{\Delta }={\max }_{u\in V}d(u)$ be the max-degree. Let $\mathrm{\Phi }={\min }_{S\subset V}|\partial S|/\min (d(S),d(V\setminus S))$ denote the conductance where $\partial S=\{(u,v)\mid u\in S,v\in V\setminus S\}$.

Let $\pi$ and ${\tau }_{\mathrm{mix}}$ denote the stationary distribution and mixing time of the lazy random walk on the network. Recall that the lazy walk stays at the current node with probability 1/2, otherwise it moves to a uniformly random neighbor; see, Algorithm 2 for a reference. As the name implies, once the random walk reaches the “stationary” distribution, it stays there forever; for the lazy walk, it is known that $\pi (u)=d(u)/2m$ for any node $u$ (see, e.g., [51]).

Furthermore, let $p_t(u,v)$ be the probability distribution of the lazy random walk that started at node $u$ and ended up at node $v$ after $t$ steps. In this paper, we define the mixing time ${\tau }_{\mathrm{mix}}$ as the minimum $t$ such that for all pairs of nodes $u$ and $v$, $|p_t(u,v)-\pi (u)|\le n^{-c}$, where $c$ is a suitable constant.

In any round, each node can send $O({\log }^{2}n)$ bits along any edge. We consider a slightly non-standard $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}(B)$ model [61], where $B$ is polylogarithmic in $n$ (instead of $O(\log n)$), so that the exposition of the analysis becomes simple, as each node can send $O(\log n)$ random walk tokens, having distinct node ids, in a single round.

For the sake of a clean exposition, we make a simplifying assumption that the nodes have a good estimate (i.e., within constant factors) of the network’s mixing time, $d(S)$, $n$ and $m$ (where $S\subseteq V$ is part of the input).

For the routing problem, these parameters could be estimated directly, i.e., nodes can determine the various sizes by evaluating aggregate functions (such as summation, etc), for e.g., by constructing a BFS tree using the node with minimum id as the root. For the mixing time, nodes can use a “guess-and-double” trick until all routing paths are established [32], i.e., if a node cannot route a message to its destination in the anticipated time, then the node can inform the root, which can re-initiate the routing algorithm after doubling the estimate.

There has been a vast literature on the design, analysis and applications of random walks in distributed networks. Alon et al. showed that the cover time (i.e., expected time taken to visit all nodes) can be significantly reduced over various families of graphs, when multiple (independent) simple random walks are started from an arbitrary node. However, they do not minimize congestion. In the CONGEST model, Das Sarma et. al showed that an $L$-length random walk can be computed in $\tilde{O}(\sqrt{LD})$ time, i.e., sublinear in the length of the walk, where $D$ denotes the diameter of the network. They achieved it by performing several short random walks and carefully stitching them together. In a subsequent work, Das Sarma et. al [66] extended this algorithm to dynamic regular networks, where the network can change arbitrarily over time. In fact, the idea of stitching independent random walks has been exploited in the massively parallel computation [46] and overlay models [21, 7], for an exponential speed up in computing random walks.

A closely related stochastic process is a natural generalization of simple random walk, called the coalescing-branching random walks [23, 19, 20, 55, 9]. Dutta et al. [23] initiated the study the rate of information dissemination, particularly cover time for different classes of networks. In particular, they show a cover time of $O({\log }^{2}n)$ in expander networks, whereas, the cover time for simple random walk is known to be $\mathrm{\Theta }(n\log n)$. This process begins with a branching factor $k$, and an arbitrary node is initially “active”. In any step, each active node chooses $k$ random neighbors to be active (i.e., “branching” property). However, a node can be active in any step only if it is chosen by some node in the previous step (i.e., “coalescing” property). A key difference with our distributed branching random walk is that although the tokens divide into multiple tokens over time, they never coalesce into a single token at any node. Moreover, our focus is on ensuring that the process induces low-congestion (i.e., each node sends at most polylog bits over any edge in any round), whilst achieving a different goal, i.e., randomly distributing samples (i.e., node ids) of any subset of nodes to the network.

Perhaps, a type of distributed random walk that is closest to the distributed branching random walks, are “count” random walks [45]. Here, a small set of nodes start (polynomially) many walks by associating a count parameter with a token (in addition to the id of the node that started the token). The way that many random walks, by a single node, can be executed is by treating each count in each token as an independent random walk, but merging them (if they are associated with the same id) while sending them along any edge. This technique has proven to be useful in many important contexts (in the CONGEST model), such as approximating the mixing time [59], leader election with sublinear message bounds [45, 36], and testing of network conductance [26, 8]. An important observation in all those works, is that at most $\tilde{O}(1)$ number of nodes start the count random walks. Thus, regardless of the count values in the tokens, the number of tokens with distinct ids traversing the network is always low (due to merging of tokens). However, amoeba-walk tokens can be started by any (polynomial) number of nodes (with distinct ids), which makes the problem of maintaining low-congestion much harder to achieve, even if merging of tokens is allowed.

While early solutions to permutation routing over expander networks were randomized [31, 32], recent works have also designed efficient deterministic algorithms [14, 12]. Since our solution uses, as a black-box, the permutation routing algorithm designed for the entire network, we provide a high-level overview of the algorithm.

The randomized algorithms work by recursively embedding Erdős-Rènyi random graphs $𝒢(n,p)$ (whilst deterministic solutions work with embedding an expander graph), on a base graph $G_0$, using random walks. In particular, the base graph $G_0$ is a random graph $𝒢(m,d/m)$ with a parameter $d=\exp (\mathrm{\Theta }(\sqrt{\log n}))$, constructed over the edge-set [32]. Then, a graph $G_1$ is embedded onto $G_0$ with low congestion and dilation, where $G_1$ is a disjoint union of random graphs $G_1^i$’s, where $G_1^i$ is a random graph $𝒢(|V_i|,d/4|V_i|)$ over the set of nodes $V_i$, where $V_1,V_2,\mathrm{\dots },V_k$ form a partition of $V$, and for all $i,|V_i|=\mathrm{\Theta }(m/k)$. Such a hierarchical decomposition recursively proceeds until the graphs have a size of roughly $\exp (\mathrm{\Theta }(\sqrt{\log n}))$. Finally, a routing mechanism is given using standard packet-routing techniques, i.e., randomized mapping of address space (e.g., [68, 43, 64]) and random-delay packet routing [48].

The notion of cut and flow vertex sparsifiers were introduced in the seminal works of [57, 49]. Let $G=(V,E)$ be a network, and terminal set $K\subset V$, then informally, the problem is to construct a graph $H=(V_H,E_H)$ that preserves (i.e., bounded by a small multiplicative factor) the minimum congestion of flows for any demand that is restricted to the terminals. Note that for any given demand, there exists an optimal “flow assignment,” i.e., a set of paths along which messages from a source to a terminal are routed. Here, the optimality is defined with respect to minimizing the congestion objective²²2For formal definitions in vertex sparsification, we refer to [58]., which is defined as the maximum congestion over all edges, and the congestion of any edge is the total flow sent over that edge (divided by its capacity).

The main idea is that if a combinatorial optimization problem depends only on the flows (or cuts) of a subset of vertices, called terminals, then an algorithm for that problem can be run on $H$ (after having precomputed such a sparsifier), instead of $G$, thereby significantly reducing the runtime, as $|V_H|\approx |K|\ll |V|$. Such a fundamental “network compression” primitive has received a great deal of attention since its inception (see, e.g., [24, 15, 52, 18, 1, 44, 17]).

In comparison with our work, we point out a few differences with flow sparsification. First and foremost, we consider identifying a subgraph, i.e., $V_H\subseteq V$ and $E_H\subseteq E$ in the distributed setting, where nodes have only local knowledge. Second, another key difference is that our focus is on minimizing the completion-time objective, i.e., the time taken for the last message to reach its destination, which is a function of both congestion and dilation (i.e., length of the paths). We refer to the recent works of [30, 40] for more details on this objective (and how it is strongly desirable in packet routing in networks). Finally, we consider preserving the minimum completion-time for permutation demands, and not arbitrary demands.

If the set of nodes $S$ are “close together” in the network, and if $|S|$ is large enough, when the tokens have a high count and are dividing into multiple tokens, there are nodes in $S$ that end up getting a large number of tokens (from many distinct nodes). The key idea is to shift our focus from a collection of tokens to individual tokens of count value equal to one from round 1, i.e., each count is indeed executing a lazy random walk (though the random choice may be correlated with other counts).

Let the initial count (in round 1), started by nodes in $S$, be denoted as $𝒞\in \mathbb{N}$. For the sake of analysis, the initial count started by node in $S$, is viewed as a collection of individual counts, indexed by $[𝒞]$. Let $C_t(u,v)$ be the random variable for the total count of node $u$ (over all tokens present) at any node $v\in V$ in any round $t\ge 1$. Let $C_t(u,v,k)$ be the indicator random variables for the presence of the count $k$ of node $u\in S$ at any node $v\in V$ in any round $t\ge 1$. Let ${\mathrm{P}}_{i,j}(u,v)$ denote the probability that a lazy random walk that starts at node $u$ in round $i$ and ends at node $v$ in round $j$, for $j>i$. Let $\mathrm{sgn}(x)=0$ if $x$ is even, and $1$ otherwise. Let $B(u,r)=\{v\mid 0\le \mathrm{𝑑𝑖𝑠𝑡}(u,v)\le r\}$ be the ball of radius $r$ around a node $u$, where $\mathrm{𝑑𝑖𝑠𝑡}(u,v)$ denotes the distance between nodes $u$ and $v$ in $G$. Let $ϵ=\mathrm{\Phi }/\mathrm{\Delta }$ and $h=\lceil {\log }_{1+ϵ}10ℬ\rceil$ where $ℬ=\mathrm{\Omega }({\log }^{c}n)$; note $\forall u\in V,|B(u,H)|\ge 10ℬ$.

Consider some node $v_0\in V$ and $|S|=\lfloor \sqrt{n}\rfloor$. Let $r_0={\mathrm{argmin}}_r(|B(v_0,r)|\ge |S|)$. Let $S$ be the set of nodes closest to the node $v_0$ among nodes in $B(v_0,r_0)$, including node $v_0$, where $|S|\ge \lfloor \sqrt{n}\rfloor$. Let $S_{\mathrm{𝑒𝑣𝑒𝑛}}=\{w\mid \mathrm{sgn}(\mathrm{𝑑𝑖𝑠𝑡}(v_0,w))=0\wedge (w\in S)\}$ and $S_{\mathrm{𝑜𝑑𝑑}}=S\setminus S_{\mathrm{𝑒𝑣𝑒𝑛}}$. By pigeonhole principle, either $S_{\mathrm{𝑒𝑣𝑒𝑛}}\ge 5ℬ$ or $S_{\mathrm{𝑜𝑑𝑑}}\ge 5ℬ$. If $S_{\mathrm{𝑒𝑣𝑒𝑛}}\ge 5ℬ$, then $S^{\prime }=S_{\mathrm{𝑒𝑣𝑒𝑛}}$ and $b=0$, whereas if $S_{\mathrm{𝑜𝑑𝑑}}\ge 5ℬ$, then $S^{\prime }=S_{\mathrm{𝑜𝑑𝑑}}$ and $b=1$. Furthermore, if $\mathrm{sgn}(h)=b$, then $h^{\prime }=h$, whereas if $\mathrm{sgn}(h)\ne b$, then $h^{\prime }=h-1$.

As each count is executing a lazy random walk, for any nodes $u\in S$ and $v\in V$, and any count $k\in [𝒞]$, $𝔼[C_t(u,v,k)]={\mathrm{P}}_{1,t}(u,v)\ge 1/{(2\mathrm{\Delta })}^t$. By linearity of expectation, and due to max-degree $\mathrm{\Delta }$, the following two claims hold: (1) $\forall u\in S$, if , then $𝔼[C_t(u,v_0)]\ge \lfloor 𝒞/{(2\mathrm{\Delta })}^t\rfloor$, and (2) $\forall u\in S$, if $0\le \mathrm{𝑑𝑖𝑠𝑡}(u,v_0)\le t\le h-2$ and $\mathrm{sgn}(t)=\mathrm{𝑑𝑖𝑠𝑡}(u,v_0)$, then $𝔼[C_{t+2}(u,v_0)]\ge 𝔼[C_t(u,v)]/4{\mathrm{\Delta }}^2$. By combining the two claims, and the bound on conductance, $\forall u\in S^{\prime }$, $𝔼[C_{h^{\prime }}(u,v_0)]\ge \lfloor \mathrm{\Theta }(\sqrt{n}\log n)/{(2\mathrm{\Delta })}^{h^{\prime }}\rfloor =\mathrm{\Omega }(\log n)$, as $\mathrm{\Delta }=O(1)$ and $\mathrm{\Phi }=\mathrm{\Omega }(1)$, ${(2\mathrm{\Delta })}^{{\log }_{1+ϵ}10ℬ}\ll \sqrt{n}$. Thus, the node $v_0$ needs to send tokens from $ℬ=\mathrm{\Omega }({\log }^{c}n)$ distinct nodes in round $h^{\prime }+1$, in expectation. $◀$

For showing that amoeba-walks can have low-congestion, we rely on a useful property about multiple lazy random walks. Informally, it says that if each node $u$ starts with roughly $\mathrm{\Theta }(d(u)\log n)$ random walk tokens (i.e., the collective set of tokens³³3Here, we mean the distribution of tokens, i.e., the number of tokens at any node divided by the total number of tokens in the network., in the network, are roughly already initially in stationary distribution), then in any round $t$, the expected number of tokens at any node $u$ is at most $O(d(u)\log n)$; if $t\le \mathrm{poly}(n)$, this property also holds, whp. Indeed, variants of this property appear in different contexts of distributed networks, including overlay networks (e.g., [6, 21]) and distributed property testing (e.g., [10]).

For the sake of analysis, at the start, add “virtual” tokens to each node until each node $u$ has $2B_u=\mathrm{\Theta }(d(u)\log n)$ (real or virtual) tokens. Note that adding additional tokens can only increase the congestion. Without loss of generality, let the initial vector of tokens is $ℬ=(2B_{u_1},\mathrm{\dots },2B_{u_n})$. Further, let $T$ be the lazy random walk transition matrix of $G$; it is well-known that the stationary distribution vector is $\pi =(d(u_1)/2m,\mathrm{\dots },d(u_n)/2m)$. Using the property of the stationary distribution, we know that $\pi \cdot T=\pi$. With the help of this fact, we can bound the expected number of tokens at any node.

Let $X_u^t$ the number of tokens at node $u$ in round $t$. Let ${𝒳}_t=(X_{u_1}^t,\mathrm{\dots },X_{u_n}^t)$ denote the vector of tokens in round $t$. We can show the following statement via induction for any $t\ge 1$,

For the first round, the statement is trivially true. Moreover, from any round to the next, an elementary calculation reveals that,

Now we use the fact that ${ℬ}_0$ is proportional to the stationary distribution,

Thus, for any round $t$, $𝔼[X_u^t\mid {𝒳}_1=ℬ]=2B_u$. Since the mixing time of lazy random walk is at most polynomial in $n$ [51], $t=\tilde{O}({\tau }_{\mathrm{mix}})\le \mathrm{poly}(n)$. As $X_u^t$ is a sum of binary independent random variables over all tokens on all nodes, by Chernoff bounds (cf. Section A) and union bound, the number of tokens at any node $u$ in any round $t$ is $O(d(u)\log n)$ whp. $\mathrm{⊲}$

To prove that amoeba-walks, for a parameter $L=\mathrm{\Theta }({\tau }_{\mathrm{mix}})$, respects the congestion requirements, we exploit a careful alternation between the reliance on individual (i.e., for “divide” phase) and collective (i.e., for “mix” phase) probability distribution of tokens.

We analyze the algorithm in $O(\log n)$ “epochs,” where epoch $i\ge 1$ starts in round $1+(i-1)L$, i.e., the length of each epoch is $L$ rounds. We maintain two invariants in every epoch, whp; for every node $u\in V$, (1) at the start, node $u$ has at most $B_u=\mathrm{\Theta }(d(u)\log n)$ tokens, and (2) in any round, node $u$ has $O(B_u)$ tokens. If this can be shown, note that the first two statements (in the lemma) are proved.

Consider a stochastic process where, at most $Cm\log n$ balls are randomly thrown into $n$ bins, where $C$ is a suitably large constant. Specifically, each ball is independently placed in bin $u$ with probability $p(u)=(d(u)/2m)\pm n^{-\mathrm{\Theta }(1)}$, where ${\sum }_{v}p(v)=1$. Let $X_{i,u}$ denote the indicator random variable for ball $i$ placed in bin $u$. Let $X_u={\sum }_i{X}_{i,u}$ denote the random variable for number of balls in bin $u$. By a Chernoff bound (cf. Section A) and union bound over all balls and bins, $X_u\le \mathrm{\Theta }(d(u)\log n)=B_u$, whp, where $B_u$ denotes the “max load” on any bin $u$.

Let every node $u$ start at most $2B_u$ tokens that independently execute the lazy random walk in any round $i\ge 1$ over the network $G$. As the tokens are collectively in stationary distribution, by Claim 6, node $u$ has at most $O(d(u)\log n)$ tokens in any round, whp.

At the start of any epoch $i$, after the token-division (i.e., Line 7–9 in Algorithm 1), if at every node $u$, there are at most $2B_u$ tokens, then by the congestion analysis of lazy random walks, until the start of epoch $i+1$, the number of tokens at any node $u$ is at most $O(B_u)$, whp.

At the end of any epoch $i$, i.e., right before the next token-division in round $1+iL$, each token is (independent of other tokens) “well-mixed,” as it traversed the network for $\mathrm{\Theta }({\tau }_{\mathrm{mix}})$ rounds (i.e., from the start to end of epoch $i$). In other words, the probability of that token ending up at any node $u$ at round $1+iL$ is $(d(u)/2m)\pm n^{-\mathrm{\Theta }(1)}$ (cf. Section 2). Thus, we can recover the bound $B_u$ on the number of tokens at any node $u$ at the start of epoch $i+1$ by the aforementioned weighted balls-and-bins process, with high probability. Finally, by a union bound on all rounds, $\mathrm{𝐀𝐦𝐨𝐞𝐛𝐚}\text{-}\mathrm{𝐖𝐚𝐥𝐤}(S,\mathrm{\Theta }({\tau }_{\mathrm{mix}}))$ acheives the congestion bounds in every round, with high probability.

Finally, as there are (totally) $\mathrm{\Theta }(m\log n)$ tokens in final phase, with each of them having independently executed lazy random walk, the third statement holds, whp, again due to the weighted balls-and-bins process. $◀$