This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that deterministically guarantee a polylog-competitive completion-time:

The packet routing problem asks to select routing paths that minimize the maximum edge congestion for a set of packets specified by source-destination vertex pairs. We revisit a semi-oblivious approach to this problem: each source-destination pair is assigned a small set of well-chosen predefined paths before the demand is revealed, while the sending rates along the paths can be optimally adapted to the demand. This approach has been considered in practice in network traffic engineering due to its superior robustness and performance as compared to both oblivious routing and traditional traffic engineering approaches.

This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only logO(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.

Abstract In this paper, we refine the (almost) existentially optimal distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n -node graph with shortcut quality $$\textrm{SQ}(G)$$ SQ ( G ) can be solved after $$n^{o(1)} \text {SQ}(G) \log (1/\epsilon )$$ n o ( 1 ) SQ ( G ) log ( 1 / ϵ ) rounds, where $$\epsilon >0$$ ϵ > 0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires $$\widetilde{\Omega }(\textrm{SQ}(G))$$ Ω ~ ( SQ ( G ) ) rounds, even for a crude solution with $$\epsilon \le 1/2$$ ϵ ≤ 1 / 2 . Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in $$D \cdot n^{o(1)} \log (1/\epsilon )$$ D · n o ( 1 ) log ( 1 / ϵ ) rounds, where D is the hop-diameter of the network; as well as $$n^{o(1)} \log (1/\epsilon )$$ n o ( 1 ) log ( 1 / ϵ ) -round algorithms for the case of $$\textrm{SQ}(G) \le n^{o(1)}$$ SQ ( G ) ≤ n o ( 1 ) , which holds for most networks of interest. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated cli

We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in Õ(D + √n ) rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai [STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in Õ(D) rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family.

This paper refines the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if ε > 0 is the error of the Laplacian solver, we obtain two main results.

We provide universally-optimal distributed graph algorithms for (1+∊)-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any n-node network G, our algorithm completes in T · no(1) rounds whenever a T-round algorithm exists for G. This includes D · no(1)-round algorithms for any planar or excluded-minor network. Our algorithms never require more than rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient no(1)-competitive linear ℓ1-oblivious routing operator that does not require the use of ℓ1-embeddings. Our construction is simple, solely based on low-diameter decompositions, and—in contrast to all known constructions—directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

This paper presents near-optimal deterministic parallel and distributed algorithms for computing (1+eps)-approximate single-source shortest paths in any undirected weighted graph.

We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing.

Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hop-unconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hop-constrained distances in graphs are very far from being a metric.

Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions:

We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.

In classical secretary problems, a sequence of n elements arrive in a uniformly random order, and we want to choose a single item, or a set of size K. The random order model allows us to escape from the strong lower bounds for the adversarial order setting, and excellent algorithms are known in this setting. However, one worrying aspect of these results is that the algorithms overfit to the model: they are not very robust. Indeed, if a few "outlier" arrivals are adversarially placed in the arrival sequence, the algorithms perform poorly. E.g., Dynkin’s popular 1/e-secretary algorithm is sensitive to even a single adversarial arrival: if the adversary gives one large bid at the beginning of the stream, the algorithm does not select any element at all. We investigate a robust version of the secretary problem. In the Byzantine Secretary model, we have two kinds of elements: green (good) and red (rogue). The values of all elements are chosen by the adversary. The green elements arrive at times uniformly randomly drawn from [0,1]. The red elements, however, arrive at adversarially chosen times. Naturally, the algorithm does not see these colors: how well can it solve secretary problems? We show that selecting the highest value red set, or the single largest green element is not possible with even a small fraction of red items. However, on the positive side, we show that these are the only bad cases, by giving algorithms which get value comparable to the value of the optimal green set minus the largest green item. (This benchmark reminds us of regret minimization and digital auctions, where we subtract an additive term depending on the "scale" of the problem.) Specifically, we give an algorithm to pick K elements, which gets within (1-ε) factor of the above benchmark, as long as K ≥ poly(ε^{-1} log n). We extend this to the knapsack secretary problem, for large knapsack size K. For the single-item case, an analogous benchmark is the value of the second-largest green item. For value-maximization, we give a poly log^* n-competitive algorithm, using a multi-layered bucketing scheme that adaptively refines our estimates of second-max over time. For probability-maximization, we show the existence of a good randomized algorithm, using the minimax principle. We hope that this work will spur further research on robust algorithms for the secretary problem, and for other problems in sequential decision-making, where the existing algorithms are not robust and often tend to overfit to the model.

Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge $e$ exists, we need to perform an expensive test, in which case the edge $e$ appears independently with a \emph{known} probability $p_e$. Given a budget on the total cost of the tests, our goal is to find a testing strategy that maximizes the expected maximum matching size. The above application is an example of the stochastic probing problem. In general the optimal stochastic probing strategy is difficult to find because it is \emph{adaptive}---decides on the next edge to probe based on the outcomes of the probed edges. An alternate approach is to show the \emph{adaptivity gap} is small, i.e., the best \emph{non-adaptive} strategy always has a value close to the best adaptive strategy. This allows us to focus on designing non-adaptive strategies that are much simpler. Previous works, however, have focused on Bernoulli random variables that can only capture whether an edge appears or not. In this work we introduce a multi-value stochastic probing problem, which can also model situations where the weight of an edge has a probability distribution over multiple values. Our main technical contribution is to obtain (near) optimal bounds for the (worst-case) adaptivity gaps for multi-value stochastic probing over prefix-closed constraints. For a monotone submodular function, we show the adaptivity gap is at most $2$ and provide a matching lower bound. For a weighted rank function of a $k$-extendible system (a generalization of intersection of $k$ matroids), we show the adaptivity gap is between $O(k\log k)$ and $k$. None of these results were known even in the Bernoulli case where both our upper and lower bounds also apply, thereby resolving an open question of Gupta et al.

The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random. In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a non-adaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of $\mathrm{poly}(\log Δ, \log \log n)$ rounds where $n$ is the number nodes in the network and $Δ$ is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not non-adaptive, it can be simulated with a multiplicative $O(Δ\log ^2 Δ)$ cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of $o(\log Δ)$ are unlikely to exist by proving that an $Ω(\log Δ)$ multiplicative round overhead is necessary under certain natural assumptions.

The widely-studied radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this model, the strong assumption is made that node v receives a message from a neighbor if and only if exactly one of its neighbors broadcasts. We relax this assumption by introducing a new noisy radio network model in which random faults occur at senders or receivers. Specifically, for a constant noise parameter p ∈ [0,1), either every sender has probability p of transmitting noise or every receiver of a single transmission in its neighborhood has probability p of receiving noise.

Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA'16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive Omega(√n + D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed optimization algorithms on such topologies, e.g., for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner.