Expander Routing under Adversarial Deletions via Temporal Aggregation

Introduction

In the routing problem, we are given a graph and pairs of nodes in this graph, called demands, between which we need to establish paths. The challenge is to come up with paths that are short but also have low congestion, i.e., the maximal number of paths passing through a given edge.

The latter is not always achievable. For example, a node may participate in far more demands than its degree allows, or there may be a small cut separating many demand endpoints. This motivates restricting attention to graph classes in which the cut obstruction does not arise once the per-vertex feasibility condition holds. In particular, one can study graphs for which, whenever every node $v$ is the source of at most $\operatorname{deg}(v)$ demands, there is no sparse cut separating many demand endpoints. Such graphs are (essentially) expanders, and the resulting restriction of the routing problem is known as expander routing. Remarkably, these necessary conditions are also sufficient: expander routing always admits a solution with polylogarithmic congestion and path length. Moreover, in the static setting—where the graph and the demand set are fixed—such a solution can be computed in polynomial time [5].

Practical systems, however, are rarely static. Demands typically arrive and depart over time, and the underlying network itself may change. The challenge is even sharper under an adaptive adversary that observes the algorithm’s current state and chooses updates intended to force failure. A trivial approach is to recompute a full routing after every update, but this can incur large and unnecessary overhead. This leads to the following question:

Can we maintain expander routing efficiently under adaptive adversarial updates?

We answer this in the affirmative. Concretely, we give a maintenance scheme that preserves polylogarithmic congestion and path length while requiring only polylogarithmic amortized computation per adversarial update.

Dynamic Expander Routing Problem

We now formally define the dynamic expander routing problem. Initially, the algorithm is given a graph $G_1$ on $n$ vertices and a set of demands $\mathcal{D}_1 \subseteq V(G_1) \times V(G_1)$. The algorithm may perform a polynomial-time setup phase, after which it outputs a collection of paths $\mathcal{P}_1$ in $G_1$ such that every demand $(s,t) \in\mathcal{D}_1$ is served by some path $p \in\mathcal{P}_1$, meaning $p$ connects $s$ and $t$.

The process evolves over $T = \operatorname{poly}(n)$ time steps. At each time step $1 < t \leq T$, an adaptive adversary—having observed the current maintained paths—modifies the instance. Specifically, it deletes some edges from $G_{t-1}$ to obtain a new graph $G_t$, and it may also add or delete demands from $\mathcal{D}_{t-1}$ to obtain a new demand set $\mathcal{D}_t$. After these changes, the algorithm must update its solution from $\mathcal{P}_{t-1}$ to $\mathcal{P}_t$ so that every demand in $\mathcal{D}_t$ is served.

The goal is to maintain a set of paths $\mathcal{P}_t$ with small dilation, i.e., the maximal path length, and small congestion, i.e., the maximum number of paths passing through any edge, at all times, while also minimizing the computation performed after the setup phase.

Adversary constraints. We impose three constraints on the adversary. First, we assume a feasibility condition on demand endpoints:

Without this assumption, the degree of a single node becomes an unavoidable bottleneck, and low-congestion routing cannot be guaranteed.

Second, we require that the graph remains an expander.

This assumption can be ensured via expander pruning [SW19]: after the adversary deletes edges, a pruning procedure may delete additional edges to restore expansion. Notably, if the adversary deletes $q$ edges in total, then pruning deletes $\widetilde{O}(q)$ edges and performs $\widetilde{O}(q)$ computation in total.

Once we allow deleting $\widetilde{O}(q)$ edges in addition to adversary, we can as well assume that $q \leq\frac{|E(G_1)|}{\log^c n}$, for some constant $c$, since once $q$ reaches this threshold, we can delete all $|E(G_1)|$ edges and leave the graph empty.

Concretely, it suffices to take $c = c_0 + 1$, where $c_0$ is the constant such that, after $q$ deletions, the number of touched hypercube edges is at most $q \log^{c_0} n$ (Lemma 4); see the proof of Lemma 3.

Dynamic Hypercube Embedding Problem

We show that dynamic expander routing can be reduced to a structured special case, namely dynamic generalized hypercube embedding. A generalized hypercube is a graph that retains the hierarchical, bit-fixing-like connectivity of a hypercube, but is defined for an arbitrary number of vertices (not necessarily a power of two).

For convenience, in this work, we sometimes refer to a generalized hypercube simply as a hypercube.

In the dynamic hypercube embedding problem, the algorithm is presented with a sequence of undirected graphs $G_1,G_2,\ldots,G_T$, revealed online. The sequence is chosen by an adaptive adversary: each graph $G_t$ is obtained from $G_{t-1}$ by deleting a subset of edges after observing the algorithm’s behavior on $G_{t-1}$. However, for every $t \in[T]$, the graph $G_t$ is guaranteed to be a good expander, that is, its mixing time satisfies $\tau_{\mathrm{mix}}(G_t) \le\tau_{\mathrm{mix}}$, where $\tau_{\mathrm{mix}} = \operatorname{polylog}(n)$ is a known global bound.

At each step $t > 1$, the algorithm must construct an embedding of a generalized hypercube $H_t$ onto $G_t$. For $t = 1$, we assume that the embedding is given. The embedding consists of a bijection $\xi_t : V(H_t) \to E(G_t)$ that assigns each hypercube vertex to a unique edge of $G_t$. Further, for every hypercube edge $(u,v) \in E(H_t)$, the algorithm must specify a path in $G_t$ connecting $\xi_t(u)$ and $\xi_t(v)$.

The objective is to minimize, over all time steps, the maximum congestion and maximum dilation of the maintained paths, as well as the total computation performed across the update sequence.

Our Results

Our main result gives an efficient solution to dynamic expander routing against an adaptive adversary, optimal up to polylogarithmic factors.

A key building block is the ability to maintain, dynamically, a low-congestion and low-dilation embedding of a generalized hypercube into the changing expander.

We now give a high-level overview of how we achieve these results.

Our Approach

Reducing to routing in hypercube. A central special case of static expander routing is routing in the hypercube, which admits a particularly simple scheme due to Valiant. To route between two vertices $s$ and $t$, one samples a uniformly random intermediate vertex $w$ and routes from $s$ to $t$ via $w$, using a bit-fixing path from $s$ to $w$ and from $w$ to $t$. Under this scheme, if each node participates in at most $O(\log n)$ demands, then the congestion and dilation are $O(\log n)$ w.h.p.

Our approach leverages this idea in a two-step manner. First, we maintain an embedding of a virtual generalized hypercube into the underlying expander. Second, we route demands in this virtual hypercube using a Valiant-like strategy, and then project the resulting hypercube route back to the original expander using the maintained embedding.

To illustrate the reduction, consider serving a demand $(s,t) \in V(G) \times V(G)$. Choose arbitrary edges incident to $s$ and $t$, say $e_1$ and $e_2$. Using the embedding $\xi$, we translate these to hypercube vertices $\xi^{-1}(e_1)$ and $\xi^{-1}(e_2)$, route between them in the (virtual) hypercube, and then map each hypercube edge to its projection in $G$. This yields a valid route from $s$ to $t$ in the original expander.

Using Temporal Aggregation. Both in hypercube embedding and in hypercube routing, our constructions rely on random walks. In the static setting, random walks are an attractive tool: they naturally spread load and prevent any single edge from becoming overly congested. In the dynamic setting with an adaptive adversary, however, this robustness can break down. Since the adversary observes the algorithm’s current state, it can trigger repeated resampling of a walk—for example, by deleting an edge currently used by that walk—and thereby bias the maintained set of walks toward a chosen region of a graph, thus overcongesting it.

Vector (PDF)

One particularly damaging strategy is a resample-until-hit attack, where the adversary repeatedly forces resampling until a chosen walk happens to traverse a targeted edge, and then repeats this process across many walks to accumulate congestion on that edge. To defend against such attacks, the algorithm must resample random walks proactively.

To this end, we employ a recent framework known as Temporal Aggregation [13]. This scheme performs few proactive resamples, ensuring, however, regardless of the adversary’s strategy, that the collection of maintained random walks induces low congestion at every time step with high probability.

Related Work

Static General Graph Routing. The field of routing was hugely pioneered by Räcke [Rac02, Rac08] whose endeavor culminated in designing a routing scheme for general graphs, that can produce a set of paths to serve the demands in polynomial time with congestion that is only a factor of $O(\log n)$ greater than the optimal congestion for the given problem instance. Furthermore, Räcke’s scheme is oblivious, meaning the algorithm’s choice of path for a particular demand does not depend on the choices for other demands.

However, Räcke’s results do not capture the dilation of paths. This gap was addressed in a work by Ghaffari, Haeupler, and Zuzic [10], which provides a polynomial time oblivious scheme that is $\widetilde{O}(1)$ competitive against the optimal congestion + dilation for the problem instance.

This result was further adapted to a CONGEST model [14] with an additional property of every node storing only a little additional information.

Static Special Case Routing. The first work on oblivious routing is by Valiant and Brebner [VB81], who gave an elegant way to route demands in a hypercube with $O(\log n)$ dilation and congestion whp. Other special case results include studies on hole-free graphs [1], geometric graphs [2], meshes [3], and other [15 Sch06, Upf84, Rac09].

Static Expander Routing. The expander routing problem was first studied by Ghaffari et al. [11] who considered it in the CONGEST model. There, the demand $(u,v)$ means that $u$ wants to send a token to $v$, and the goal is to send all the tokens in as few rounds as possible. In [11], the round complexity of the problem was shown to be $\tau_{\min}(G)\cdot2^{O(\sqrt{\log n}\cdot\log\log n)}$ with $\tau_{\min}(G)$ being a mixing time of the underlying graph $G$. This was further improved by [12], which achieves $\tau_{\min}(G)\cdot2^{O(\sqrt{\log n})}$ rounds. Algorithms in [11] and [12] are randomized, which was addressed in works [9, 5] that obtained a deterministic CONGEST algorithm for expander routing in $O(\operatorname{poly}(\phi^{-1}(G))\cdot2^{O(\sqrt{\log n}\cdot\log\log n)})$ rounds with $\phi(G)$ being a conductance of the underlying graph $G$.

Overall, expander routing has proven to be useful in many applications, such as distributed MST construction [11], subgraph finding [7, 8], and various data-summarization tasks [SV19]. Further, expander routing allows us to transform a large class of work-efficient PRAM algorithms into CONGEST algorithms with small overhead [12], perform a smooth analysis for distributed MST [6], and design sparsity-aware algorithms for various shortest path computation tasks in the CONGEST model [4].

Preliminaries and Notation

We use $n$ as an upper bound on the number of vertices in $G_t$ for all $t$. One can assume $n := |V(G_1)|$. Similarly, $m$ is the upper bound on the number of edges in $G_t$. Since we assume $G$-s to be connected, we use $O(\log n)$ instead of $O(\log m)$ everywhere. When the exact time step is not relevant, we omit specifying it and simply write $G$ and $H$. We use $\widetilde{O}$ notation to hide polylogarithmic factors. By with high probability (w.h.p.) we mean the probability of at least $1 - \frac{1}{n^c}$ for some $c \ge1$.

A random walk on a graph is a discrete process that starts at some vertex and, at each step, travels to a uniformly random neighbor of the current vertex. A lazy random walk is the one that, alternatively, with probability $1/2$, stays at the same vertex. It is known that the distribution of a lazy random walk converges to a stationary distribution in which each vertex $v \in G$ has a probability $\frac{\deg_G(v)}{2|E(G)|}$. Alternatively, we will sometimes speak about edge random walks, the difference being that the random walk starts from an edge and travels to an adjacent edge. The reason to shift to this perspective is that the edge random walk possesses a uniform stationary distribution over edges, which is convenient to work with.

The mixing time of $G$, denoted $\tau_{\mathrm{mix}}(G)$, can be defined as the number of time steps for (any) initial distribution of a random walk on $G$ to get inverse-polynomially close to the stationary one in the sense of $L_2$ distance. With that, expanders can be defined as graphs having polylogarithmic mixing time. In some of our derivations, we implicitly assume $\tau_{\mathrm{mix}} = \widetilde{O}(1)$.

Throughout the paper, we will refer to classical Chernoff bounds.

Given an embedding $\xi$ of a hypercube $H$, we sometimes slightly abuse the notation and write $\xi(e)$ for $e \in E(H)$ to refer to the path in $G$ to which $e$ is mapped by the embedding. We call this path a projection of $e$ or a path corresponding to $e$, and we define a projection of a path in $H$ to be a concatenation of projections of edges constituting this path.

Temporal Aggregation. A key tool we will use repeatedly is Temporal Aggregation. The motivation is the following. Our algorithms are randomized and rely on randomness for load balancing. In a static setting, where all random choices are made simultaneously, standard concentration arguments imply that the maximum load is small with high probability. In a dynamic setting with an adaptive adversary, however, this guarantee can break down: if the adversary is allowed to repeatedly resample outcomes after observing them, it can bias the realized distribution and create excessive load.

We illustrate this issue with two examples that are central to this paper. First, consider Valiant routing on the hypercube. If all demands are routed simultaneously, then with high probability, the maximum congestion is low. In the dynamic setting, an adversary that observes the current $u$–$v$ path can force it to be resampled, e.g., by deleting an edge on it or by deleting and re-inserting the demand $(u,v)$. It can then repeat this until the path traverses some fixed target edge $e$, and then proceed similarly for other pair $u',v'$, and so on. In polynomially many steps, this can force many routes to traverse $e$, thereby overcongesting it.

As a second example, consider maintaining random walks in a graph that changes over time. Suppose that from each node we want to maintain $O(\log n)$ random walks of length $\ell$. If all these walks are sampled simultaneously, then with high probability the maximum congestion is $O(\ell\log n)$. But the same “resample-until-hit” attack applies here as well. Moreover, if the adversary can delete edges, it can increase the probability of certain random walks to hit a given edge.

In both examples, it is natural for the algorithm to resample random paths from time to time in order to “refresh” the randomness and prevent the adversary from drifting too far from the intended distribution. However, fully resampling the entire system after every adversarial update would be prohibitively expensive.

To address this, we use the Temporal Aggregation framework of [13], which was designed specifically for maintaining randomness in dynamic systems against adaptive adversaries.

The framework in [13] is as follows. The system consists of $n$ objects and evolves in discrete time steps. At each time, an object corresponds to an element in some ground set, we call this element the realization of an object. At time $t$, after observing the state of the system at time $t-1$, the adversary specifies a distribution over the ground set for each object and resamples a subset of objects according to these distributions. Then, the algorithm may also resample a subset of objects of its choice, according to the specified distributions. Objects that are not resampled at time $t$ keep their previous realizations. The set of all objects’ realizations at time $t$ is called a joint realization, and the set of all objects’ realizations at time $t$ given they are all sampled at time $t$ is called a static realization.

This formalism matches our needs. For instance, in the dynamic random-walk example, the objects correspond to individual random walks; their distributions are determined by the current graph; and objects’ realizations come from a ground set of all paths of length $l$. The quantity we care about is the maximum congestion, which corresponds to the notion of load in [13]. In our setting, the static realization has a load of $O(l \log n)$ whp, and we want to minimize the load of a joint realization.

The paper [13] provides a resampling strategy called Greedy Temporal Aggregation. Informally, if sampling all objects simultaneously would yield low load with high probability at each time, then Greedy Temporal Aggregation guarantees that the load remains low even in the dynamic, adversarially adaptive setting, at the cost of only a logarithmic-factor blow-up in both load and the number of resamples.

Theorem 3 is stated for a fixed time $T$. Applying it at every time $t \le T$ and taking a union bound, the load bound holds simultaneously at all times $t \in[T]$ with probability at least $1-\varepsilon T^2$. Since in our applications $T=\operatorname{poly}(n)$ and $\varepsilon=n^{-c}$ for an arbitrarily large constant $c$, this is still a high-probability guarantee. Whenever we invoke the theorem “at any point in time” below, we mean this simultaneous version.

To illustrate the power of this result, we show how this theorem allows us to extend static oblivious routing guarantees to a dynamic setting with an adaptive adversary essentially “for free,” up to logarithmic factors.

Proof. We map our setting to the framework of [13]. Each demand is an object. We say an object is adversarially resampled whenever the adversary either (i) introduces a new demand, or (ii) deletes an edge that the demand’s current path uses. Resampling an object corresponds to recomputing its route using the oblivious routing scheme. The load at time $t$ is the maximum congestion of the current collection of paths at time $t$.

Applying Greedy Temporal Aggregation, Theorem 3 implies that at any time $t$, the maximum congestion is at most $O(L\log n)$ whp. In particular, when the adversary deletes an edge, at most $O(L\log n)$ demands are resampled whp. Therefore, over $q$ edge deletions, the adversary triggers at most $O(q\cdot L\log n)$ adversarial resamples whp. By Theorem 3, the algorithm performs only an additional $O(\log n)$ factor more resamples, for a total of $O(q\cdot L\log^{2} n)$ oblivious-routing invocations whp.

We want to remark that for our needs, a slight extension of the framework of [13] is needed. Namely, [13] assumes that the set of objects is static, whereas our applications require adding and removing objects. We show in the Appendix § 7 that this extension can be assumed without losing guarantees of Theorem 3.

Dynamic Hypercube Embedding Algorithm

In this section, we describe our algorithm that solves the Dynamic Hypercube Embedding problem optimally up to polylog factors. We start by defining the notion that resembles that of a bit-fixing path:

As described in the problem statement, the adversary constructs the next graph $G_{t+1}$ in the sequence by removing some edges from $G_t$, which corresponds to node deletions in $H_t$. This imposes two subtasks: (I) ensuring the graph maintained is a generalized hypercube despite some nodes being deleted, and (II) ensuring each edge of the maintained hypercube corresponds to an existing path in the underlying graph.

We now describe how our algorithm adapts $H_t$ and the embedding. Recall that nodes of the hypercube $H$ are associated with numbers $[1,\ldots,|V(H)|]$.

Algorithm 1 Dynamic Hypercube Embedding. On $G$ Edges Deletion.

(I) Assume the vertex $u\in[|V(H_t)|]$ is deleted. If $u=|V(H_t)|$, we do nothing. Otherwise, we relabel the node $|V(H_t)|$ to $u$ but don’t change its mapping by $\xi$. We then remove all the edges adjacent to deleted and relabeled nodes and establish new edges $(u,u+2^i)$ for all $i$ such that $u+2^i\le|V(H_{t+1})|$ and similarly $(u,u-2^j)$ such that $u-2^j\ge1$.

(II) When an edge is deleted in $G_t$, it might as well invalidate some paths that were traversing it. We therefore need to fix all the edges from $H_t$ whose paths got invalidated by reestablishing those.

We now describe how to sample a path between edges $u$ and $v$ in $G$. We use this procedure for establishing paths for new edges.

The final ingredient in our algorithm is the Temporal Aggregation of newly established or fixed edges. It will be convenient for further analysis to introduce some definitions related to this algorithm.

Algorithm 2 Dynamic Hypercube Embedding. Sampling a $u-v$ path in $G$.

First, we run random walks from $u$ and $v$ of length $\tau_{\mathrm{mix}}$, getting the endpoints $u' \in E(G)$ and $v' \in E(G)$ respectively. These endpoints correspond to $\xi^{-1}(u') \in V(H)$ and $\xi^{-1}(v') \in V(H)$ respectively. Then, we sample a uniformly random node $w \in V(H)$ and construct greedy paths in $H$ between $\xi^{-1}(u')$ and $w$ and $w$ and $\xi^{-1}(v')$. If these greedy paths do not contain new edges nor edges used by some other greedy path, we establish a path between $u$ and $v$ as a concatenation of two sampled random walks and projections of two greedy paths. If either of the two greedy paths contains new edges or edges used by some other greedy path, we resample random walks and repeat this process until successful.

Algorithm 3 Dynamic Hypercube Embedding. Temporal Aggregation.

We map our setting to the framework of [13] as follows. Every edge $(u,v) \in E(H)$ of the hypercube corresponds to an object. The realization of the object $(u,v)$ at time $t$ is the path that corresponds to $(u,v)$ in $G_t$ between $\xi(u)$ and $\xi(v)$. Sampling an object means sampling a path as described above. Finally, we say that adversary adds an object $(u,v)$ at time $t$ if $(u,v)$ is a new edge added at time $t$, and we say that adversary samples an object $(u,v)$ if adversary deletes an edge in $G_t$ through which the path corresponding to $(u,v)$ was passing. In this setting, we employ Temporal Aggregation.

Proof Overview

Our goal is to show that the algorithm solves the problem optimally up to a polylogarithmic factor. Specifically, we aim to prove that all established paths have length $\widetilde{O}(1)$, that with high probability the congestion on every edge in $G$ remains $\widetilde{O}(1)$, and that the total number of computation steps is $\widetilde{O}(q)$ with high probability, where $q$ is the total number of adversarial edge deletions. In this section, we do the proof overview. We present formal statements in § 4.2.

Short paths. The path in $G$ between $u$ and $v$ consists of two random walks of length $\tau_{\mathrm{mix}}$ and projections of two greedy paths.

Since the greedy path in $H$ only passes through the untouched edges, whose paths were constructed at the initial embedding of the hypercube, the length of the path between $u$ and $v$ is at most $2\tau_{\mathrm{mix}}+D_{\mathrm{init}}\cdot L_{\mathrm{greedy}}$, where $D_{\mathrm{init}}$ is the maximal dilation of the initial embedding and $L_{\mathrm{greedy}}$ is the maximal length of a greedy path in $H$. Lemma 5 bounds $L_{\mathrm{greedy}}$ as $O(\log n)$.

Low congestion. In our analysis, we split the congestion introduced by paths into two parts: the congestion introduced by legs and the congestion introduced by the greedy path projections. The bound on the congestion from greedy path projections is straightforward. In particular, note that the number of greedy path projections passing through an edge $e \in E(G)$ is at most the number of the original edges whose projections pass through $e$, which is at most the maximal congestion of the original embedding.

To analyze the congestion coming from random walks, however, we refer to the guarantees of Temporal Aggregation, which yield the following crucial lemma:

Combined, these analyses result in the following lemma.

Few computation steps. The computation the algorithm performs can be analyzed per edge deletion. When an edge is deleted, the algorithm needs to (1) establish paths for new edges in $H$, (2) fix edges whose corresponding paths in $G$ were invalidated by an edge deletion, and (3) proactively resample edges through temporal aggregation. This way, bounding computation boils down to bounding the total number of paths to be (re)sampled and the computation needed to sample a single path.

Number of path (re)samples per edge deletion. For one edge deletion, we establish $\max\mathrm{-degree}(H)=O(\log(n))$ new edges in $H$. Furthermore, Lemma 2 tells us that w.h.p., the number of edges to be fixed because of the edge deletion is $\widetilde{O}(1)$. Finally, Theorem 3 tells us that temporal aggregation only introduces an additional $O(\log n)$ factor to the number of edges to proactively resample compared to the number of newly established and fixed edges.

Computation per path sampling. Trying to sample a path once is cheap: the algorithm runs two random walks of length $\tau_{mix}$ in $G$ and computes two greedy paths in $H$, both straightforwardly in $\operatorname{polylog}(n)$ steps. However, the subtlety is that the obtained path might get rejected in case greedy paths go through touched edges, which will cause another attempt. Therefore, we need to upper bound the number of potential retries.

Intuitively, the above lemma holds because there are few touched edges:

Formal Statements

In this section, we provide all the formal statements needed to prove that the Algorithm 1 results in low Dilation, Congestion, and Computation.

Dilation

This subsection provides formal statements that show that the dilation of the paths that correspond to edges in $H$ is small at any time. The following lemma bounds the length of greedy paths in $H$.

Proof. Consider a greedy path $u_1,\ldots,u_k$ between $u_1$ and $u_k$ with $u_1 < u_k$. Observe two things: First, $u_i < u_{i+1}$. Second, $u_{i+1}-u_i \ge2(u_{i+2}-u_{i+1})$. And since $u_k-u_1 = \operatorname{poly}(n)$, we deduce that $k = O(\log n)$.

Using this lemma, we conclude that the maximal dilation at any time is polylogarithmic:

Proof. Consider an edge $(u,v) \in E(H_t)$. The path in $G_t$ between $\xi(u)$ and $\xi(v)$ consists of two legs of length $\tau_{mix} = \widetilde{O}(1)$ and two projections of the greedy paths. Since the greedy path in $H$ only passes through the untouched edges, whose corresponding paths were constructed at the original embedding, the length of the path between $\xi(u)$ and $\xi(v)$ is at most $2\tau_{mix} + D_{orig}\cdot L_{greedy}$, where $D_{orig}$ is the maximal dilation of the original embedding, which is promised to be $\widetilde{O}(1)$, and $L_{greedy}$ is the maximal length of a greedy path in $H_t$, which Lemma 5 bounds as $O(\log n)$.

Congestion

This subsection focuses on proving that with high probability, at any point in time, the maximal congestion is low. We analyze congestion that comes from greedy paths’ projections and legs separately. The following lemma bounds the amount of congestion introduced by greedy paths’ projections.

Proof. By the algorithm, a greedy path in $H$ only takes untouched edges. This implies that if a projection of a greedy path goes through some edge $e \in E(G)$, then there exists an edge in $H$ on this greedy path which was established at time 1 and was never fixed, and its corresponding path goes through $e$. But the number of such edges that are neither newly established nor were fixed and pass through $e$ is at most the maximal congestion of the original embedding, which is guaranteed to be $\widetilde{O}(1)$. Therefore, since by the algorithm at most one greedy path in $H$ can pass through such an edge, the number of greedy path projections traversing $e$ is at most $\widetilde{O}(1)$.

The lemma below intuitively implies that one touched edge disallows a relatively small number of greedy paths to be taken by the algorithm.

Next is the lemma that bounds the number of retries before a successful sample of a path.

The latter lemma allows us to show that although the distribution of paths’ legs is different from the distribution of sample-once random walks due to their resample-until-success nature, those still induce a congestion comparable to the one induced by sample-once random walks. In particular, we get the following guarantee in the static setting.

Proof. Let $k := 2|E_t|$ denote the number of legs we need to sample. Lemma 3 tells us that with high probability, each leg from edge $e$ can be chosen out of $O(\log n)$ independent random walks from $e$. Therefore, with high probability, the congestion of all legs is no more than a congestion of $k \cdot O(\log n)$ random walks. Since each edge is a source of at most $O(\log n)$ legs, each edge is a source of $O(\log^2 n)$ random walks. Further, each random walk is of length $\tau_{\mathrm{mix}}$. The standard random walk congestion argument then tells us that the congestion of these random walks is at most $O(\tau_{\mathrm{mix}} \cdot\log^2 n)$ whp.

Combining Lemma 9 and Theorem 3, we can prove Lemma 1.

Proof. Invoke Theorem 3 with a static guarantee of Lemma 9 with a load being a congestion of edge $e$.

The next lemma summarizes the analysis and states that the total congestion is small.

Proof. We split the congestion of a given edge $e \in E(G)$ into two parts: congestion from legs and congestion from greedy paths’ projections. The congestion from legs is $\widetilde{O}(1)$ with high probability by Lemma 1, the congestion from greedy paths’ projections is $\widetilde{O}(1)$ by Lemma 7.

Computation

This subsection bounds the total computation performed by an algorithm by the polylog times the number of edge deletions performed by the adversary.

Lemma 3 states that the algorithm succeeds in establishing a path in a few tries. What is left to show is the bound on the total number of times the algorithm will attempt to sample a path.

Proof. The algorithm attempts to sample a path for three reasons: (1) It establishes an edge, (2) It fixes an edge, and (3) It resamples an edge due to temporal aggregation.

Denote the total number of newly established, fixed, and temporarily aggregated edges with $X$, $Y$, and $Z$, respectively.

The number of new edges established per deletion is $O(\log n)$, hence $X = O(q \cdot\log n)$. According to Lemma 2, w.h.p., the number of paths that need to be fixed after a single edge deletion is $\widetilde{O}(1)$, hence $Y = \widetilde{O}(q)$. Finally, according to Theorem 3, $Z = O(\log n \cdot(X + Y)) = \widetilde{O}(q)$.

We therefore get the following total computation guarantee.

Proof. By Lemma 10 we know that whp the number of path resampling attempts is $\widetilde{O}(q)$. Lemma 3 stipulates that one attempt requires $O(\log n)$ tries with high probability. Therefore, whp, the total computation is $\widetilde{O}(q)$.

Finally, we prove Theorem 2.

Proof. Apply Lemmas 6, 2, 11.

Dynamic Hypercube Routing

This section discusses routing demands in a dynamic generalized hypercube—the building block we use in our general dynamic expander routing algorithm when provided an embedding.

Problem Statement

Initially, the algorithm is given a generalized hypercube $H_1$ and a set of demands $\mathcal{D}_1 \subseteq V(H_1) \times V(H_1)$. The algorithm may perform a polynomial-time setup phase, after which it outputs a collection of paths $\mathcal{P}_1$ in $H_1$ such that every demand in $\mathcal{D}_1$ is served by some path in $\mathcal{P}_1$.

At each time step $t > 1$, an adaptive adversary—having observed the current maintained paths—modifies the instance. Specifically, it deletes some nodes and edges from $H_{t-1}$ and inserts some edges to obtain a new $H_t$. Also, it may add or delete demands to obtain a new demand set $\mathcal{D}_t$ from $\mathcal{D}_{t-1}$. After these changes, the algorithm must update its solution from $\mathcal{P}_{t-1}$ to $\mathcal{P}_t$ so that every demand in $\mathcal{D}_t$ is served.

We impose two constraints on the adversary. First, we require that every $H_t$ is a generalized hypercube. Second, for every time $t$ and every node $u \in V(H_t)$, $u$ is a source or a destination of at most 1 demand in $\mathcal{D}_t$.

The goal is to maintain a set of paths $\mathcal{P}_t$ with small maximum dilation and small maximum congestion at all times, while also minimizing the computation performed per adversarial modification (vertex deletions, edge insertions/deletions, and demand insertions/deletions).

Static Routing in Generalized Hypercube

We now give a Valiant-like oblivious routing procedure that performs well in static generalized hypercubes.

Algorithm 4 Oblivious routing from $s$ to $t$ in generalized hypercube.

$w \leftarrow$ uniformly random node $p_s \leftarrow$ greedy path from $s$ to $w$ $p_t \leftarrow$ greedy path from $w$ to $t$ Output concatenation of $p_s$ and $p_t$

This procedure results in low congestion with high probability.

Proof. Fix an edge $e \in E(H)$. We bound the number of paths that traverse $e$; a union bound over all edges then yields the maximum congestion.

Consider only the $s \to w$ segments (the $w \to t$ segments are identical by symmetry since $w$ is sampled uniformly and independently for each demand). For each demand $(s,t) \in\mathcal{D}$ define

We show $\mathbb{E}[X_e] \le2$ and then apply Chernoff.

Write $e = (a,b)$ with $a < b$ and let its stretch be $\ell= b-a = 2^i$. If $s \in(a,b)$ then a greedy path from $s$ cannot traverse $(a,b)$, so $\Pr[X_{s,e} = 1] = 0$. Now fix $s \leq a$. If the greedy path uses $(a,b)$, then upon reaching $a$ the next step must be exactly $\ell$, which by the greedy rule happens iff the remaining distance to $w$ satisfies $w-a \in[\ell,2\ell)$, i.e. $w \in[b,b+\ell)$. Hence for every $s \leq a$,

Moreover, only a few sources $s \leq a$ can reach $a$ and then take an $\ell$-jump: along a greedy path, step lengths are strictly decreasing powers of two, so before taking the $\ell$-edge, all earlier steps must have lengths in $\{2^{i+1},2^{i+2},\ldots,2^{\lfloor\log_2 n\rfloor}\}$. Choosing any subset of these lengths uniquely determines the total displacement from $s$ to $a$, hence yields at most one such source $s$. Therefore the number of sources $s \leq a$ whose greedy path can traverse $e$ is at most

Since $\mathcal{D}$ contains at most one demand per source, we get

By symmetry (reversing the order on $[n]$), the same bound holds for sources $s \geq b$, contributing at most 1 in expectation. Thus

For fixed $e$, the variables $\{X_{s,e}\}_{(s,\cdot)\in\mathcal{D}}$ are independent because the intermediate vertices $w$ are sampled independently across demands. Hence, by a Chernoff bound, there is an absolute constant $c>0$ such that

The generalized hypercube has $O(n\log n)$ edges, so a union bound implies

Therefore, with high probability, every edge has congestion $O(\log n)$ from the $s\to w$ segments. The same holds for the $w\to t$ segments, and thus the total congestion per edge is $O(\log n)$ with high probability. □

We also observe from the description of the algorithm that it takes little computation.

We remark that the Algorithm 4 can be used in the precomputation phase of the Dynamic Generalized Hypercube Routing problem, yielding $O(\log n)$ maximal congestion whp and $O(n\log n)$ precomputing time. We now explain how we maintain this routing.

Dynamic Algorithm

To lift the static routing scheme to the dynamic setting with an adaptive adversary, we use Greedy Temporal Aggregation of [13].

Algorithm 5 Dynamic Hypercube Routing

We map our setting to the framework of [13]. Each demand is an object. We say an object is adversarially added whenever the adversary introduces a new demand, or adversarially resampled if the adversary deletes an edge that the demand’s current route uses. Resampling an object corresponds to recomputing its route using the Algorithm 4. With this, we apply Greedy Temporal Aggregation.

Proof. Algorithm 5 instantiates Corollary 1 with a static routing Algorithm 4. Lemmas 12 and 13 then imply the statement of the theorem.

Putting it Together

In this section, we combine our Dynamic Hypercube Embedding and Dynamic Hypercube Routing algorithm to obtain a solution for the original Dynamic Expander Routing Problem.

Algorithm for Dynamic Expander Routing

Algorithm 6 Dynamic Expander Routing

First, in the setup phase, we do an embedding $\xi$ of a Generalized Hypercube $H_1$ onto $G_1$, e.g., according to the algorithm presented in [5]. Throughout the process, we maintain this embedding according to Algorithm 1.

The initial set of demands for $G_1$ is served as follows. For each initial demand $(u,v)$, we assign it to a spare edge $e_u$ of $u$ and a spare edge $e_v$ of $v$. Then, we serve the demand $(\xi^{-1}(e_u),\xi^{-1}(e_v))$ in $H$ by the Algorithm 4. Finally, we serve $(u,v)$ in $G$ by the projection of a path serving $(\xi^{-1}(e_u),\xi^{-1}(e_v))$ in $H$.

We will be maintaining two sets of demands—one, the set on the underlying graph $G$ called $D^G$, and one on the embedded hypercube $H$ called $D^H$. We handle serving demands from $D^H$ by Algorithm 5. We now focus on handling demands from $D^G$, given that the demands in $D^H$ are handled. When an adversary adds or deletes a demand for $G$ at time $t$, we add or delete it respectively in $D_t^G$. Also, if an adversary deletes an edge in $G_{t-1}$ through which a path serving some demand $d$ was passing, we delete and add $d$ back to $D_t^G$ explicitly.

The added demand $(u,v) \in D_t^G$ is served similarly to the initial demands. First, we assign it to a spare edge $e_u$ of $u$ and a spare edge $e_v$ of $v$. Then, we add $(\xi^{-1}(e_u),\xi^{-1}(e_v))$ to $D_t^H$. Once the demand $(\xi^{-1}(e_u),\xi^{-1}(e_v))$ is served in $H$ by Algorithm 5 via a path $p$, we serve it in $G$ by the projection of $p$.

Analysis

We now focus on analyzing the correctness of the Algorithm 6, as well as the dilation and congestion induced by it at every time, and the total computation.

Proof. We can use a Dynamic Hypercube Embedding Algorithm 1 since the graph $G$ always satisfies the low mixing time Assumption 2.

Note that for an added demand $(u,v)$ by the vertex degree feasibility Assumption 1, there will always be a spare edge $e_v$ and $e_u$. Furthermore, note that since an edge in $G$ is assigned at most one demand, a vertex in $H$ is as well, so the condition of Theorem 4 is fulfilled.

Lastly, we observe that the paths maintained by the algorithm at time $t$ indeed serve $D_t$ since the projection of a continuous path in $H$ is a continuous path in $G$ and it starts and ends at the edges incident to the endpoints of the demand.

Proof. The dilation of a path between $(u,v) \in V^2(G)$ is at most the number of edges in the hypercube path serving $(\xi^{-1}(e_u),\xi^{-1}(e_v))$ times the maximal length of the path corresponding to a hypercube edge. The prior is the length of two greedy paths, which is bounded by Lemma 5 by $O(\log n)$. And the latter is bounded by Lemma 6 by $\widetilde{O}(1)$. Hence the dilation of a path serving $(u,v)$ is $\widetilde{O}(1)$.

Proof. The congestion of an edge $e \in E(G)$ is at most the maximal number of hypercube edge projections crossing $e$ times the maximal congestion in the hypercube. The prior is bounded whp by $\widetilde{O}(1)$ by Lemma 2 and the latter is bounded by $O(\log^2 n)$ whp by Theorem 4.

Proof. We start by observing that the setup phase indeed requires polynomial time. In particular, the algorithm for the initial hypercube embedding of [5] has polynomial running time. And the initial demand serving is $O(m\log n)$ computation, since there are at most $O(m)$ demands according to Assumption 1 and the Algorithm 4 runs in $O(\log n)$ computation per demand according to Lemma 13.

After the setup phase, we have two sources of computation: maintaining the hypercube embedding and maintaining the demands in the hypercube. The first one is guaranteed to result in $\widetilde{O}(q)$ total computation with high probability by Lemma 11. To apply Theorem 4 for the second one, we first need to bound the total number of deleted edges and added demands in the hypercube. The deleted edges are straightforward: the edge is only deleted when a node is deleted, and a node in the hypercube is deleted when the corresponding edge in $G$ is deleted. Once a node in the hypercube is deleted, all the incident edges are deleted, and there are $O(\log n)$ of those. Hence, if $q$ edges are deleted in $G$, $O(q\cdot\log n)$ edges are deleted in $H$. The demand insertions are for two reasons: either it is a completely new demand inserted, or it is a reinserted demand for which an edge in $G$ on a path serving this demand was deleted. By definition, there can be no more than $q$ newly inserted demands. As for reinserted demands, Lemma 16 stipulates that whp there are at most $O(1)$ paths that are using an edge, hence per $q$ edge deletions, at most $\widetilde{O}(q)$ demands will be reinserted. This allows us to conclude that if an adversary does $q$ demand insertions and edge deletions in $G$, it does $q'=\widetilde{O}(q)$ demand insertions and edge deletions in $H$. Therefore, Theorem 4 gives us that the total computation for maintaining demands in the hypercube is $O(q'\cdot\log^4 n)=\widetilde{O}(q)$.

Finally, we prove our main theorem.

Proof. The Algorithm 6 fulfills the Theorem by Lemmas 14, 15, 16, 17.

Extending Temporal Aggregation Framework

In this section, we show that Theorem Theorem 3 holds as well if one is allowed to add and delete objects from the system. The only part of the original proof to be updated is the one concerning a few resamples done by the algorithm.

Proof of few resamples. We assume that the initial sample is at time 0.

To prove that the algorithm does a bounded number of additional samples, we conduct an amortized analysis. We say that each object has coins in its wallet and in its bequest savings. We also say that objects at time 0 have a bank.

When the adversary samples or adds an object, we assume this object receives $\log_{3/2} n$ coins to its wallet and 4 coins to its bequest from the adversary. Additionally, when the adversary samples or adds an object, it adds $3/2$ coins to the bank. Also, if the adversary samples an object that was previously sampled at time $t$ and there were $k$ objects sampled at time $t$, they all receive $4/k$ coins to their wallet from the adversary. This way, if an adversary samples or adds an object, it spends at most $\log_{3/2} n + 9\frac{1}{2}$ coins.

Further, if an adversary deletes an object that was previously sampled at time $t>0$ and there were $k$ objects sampled at time $t$, they all receive $4/k$ coins to their wallet from the bequest of the deleted object.

When an algorithm samples an object sampled at time $t$, it takes one coin from its wallet if $t>0$ or one coin from the bank if $t=0$.

Denote with $group(u)$ a set of objects sampled at the same time step as $u$ and with $wallet(u)$ the number of coins $u$ has in its wallet. Consider the potential function of $u$: $\Phi(u)=\log_{3/2}(|group(u)|)+wallet(u)$. We claim that this potential is monotonically increasing for all objects once they are sampled at time $t>0$. Indeed, consider the cases when this potential is changed.

• The object $u$ is added to the group. Then all the potentials only increase.

• The object $u$ is sampled by the adversary. Then, the $|group(u)|$ may decrease (at most) from $n$ to $1$, hence the $\log_{3/2}(|group(u)|)$ from $\log_{3/2}(n)$ to $0$, but adversary gives the object $\log_{3/2}(n)$ coins to its wallet, so $\Phi(u)$ can not decrease.

• Some other object from $group(u)$ is sampled by the adversary. Assume that before the sample $|group(u)|=k\ge2$. Then $\Delta\Phi(u)=\log_{3/2}(k-1)-\log_{3/2}(k)+4/k>0$.

• Some other object from $group(u)$ is deleted by the adversary. Assume that before the deletion $|group(u)|=k\ge2$. Then, as in the previous case, $\Delta\Phi(u)=\log_{3/2}(k-1)-\log_{3/2}(k)+4/k>0$.

• All the objects in $group(u)$ are sampled by the algorithm. This means that they are being sampled together with some other group, whose size is at least $\frac{1}{2}|group(u)|$. Therefore, the new size $|group'(u)|\ge|group(u)|+\frac{1}{2}|group(u)|=\frac{3}{2}|group(u)|$ and hence $\Delta\Phi(u)=\log_{3/2}(|group'(u)|)-\log_{3/2}(|group(u)|)-1\ge0$.

We note that if an object is deleted at time $t>0$, it was already either sampled or added, hence it has at least 4 coins in its bequest and can pay to the nodes of its group.

We can now prove that the algorithm will always be able to take a coin. First, consider sampling an object $u$ that was last sampled at time $t>0$. Indeed, we’ve shown that $\Phi(u)\ge\log_{3/2}n$. If the object is sampled, it means its group’s size is increased by at least $3/2$ times, hence it was less than $\frac{n}{3/2}$, hence the number of coins in the wallet of an object was at least 1, since $\log_{3/2}(|group(u)|)+coins(u)\ge\log_{3/2}n$ and $\log_{3/2}(|group(u)|)\le\log_{3/2}n-1$.

Next, consider an algorithm samples an object that was last sampled at time 0. Denote the group size of objects at time 0 with $n_0$, the size of some other group at time $t>0$ with which it gets merged with $n_t$. By the definition of the algorithm, we know that $n_0\le3/2n_t$. However, for every object at time $t>0$, the adversary gave to a bank $3/2$ coins, hence there are at least $3/2n_t$ coins in the bank, and we can use those to pay for sampling objects at time 0.

Finally, we conclude that