Search

The notion of Las Vegas algorithms was introduced by Babai (1979) and can be defined in two ways: * In Babai's original definition, a randomized algorithm is called Las Vegas if it has a finitely bounded running time and certifiable random failure. * Another definition widely accepted today is that Las Vegas algorithms refer to zero-error randomized algorithms with random running times. The equivalence between the two definitions is straightforward. Specifically, for randomized algorithms with certifiable failures, repeatedly running the algorithm until no failure is encountered allows for faithful simulation of the correct output when it executes successfully. We show that a similar perfect simulation can also be achieved in distributed local computation. Specifically, in the LOCAL model, with polylogarithmic overhead in time complexity, any Las Vegas algorithm with finitely bounded running time and locally certifiable failures can be converted to a zero-error Las Vegas algorithm. This transformed algorithm faithfully reproduces the correct output of the original algorithm in successful executions.

This paper presents parallel and distributed algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in either setting to $n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter $D$, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and $S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with $W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii) $T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes $T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$. This work builds off the recent result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art SSSP algorithms yields randomized algorithms for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in $\mathsf{CONGEST}$. Our main technical contribution is an efficient reduction for computing a low-diameter decomposition (LDD) of directed graphs to computations of SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models. The LDD is a crucial step of the algorithm in [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], and we think that its applications to other problems in parallel and distributed models are far from being exhausted.

We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer $\kappa$, our algorithm can, with high probability, either find $\kappa$ vertices whose removal disconnects the network or return that such $\kappa$ vertices do not exist. Our algorithm takes $\kappa^3\cdot \tilde{O}(D+\sqrt{n})$ rounds, where $n$ is the number of vertices in the network and $D$ denotes the network's diameter. This implies $\tilde{O}(D+\sqrt{n})$ round complexity whenever $\kappa=\text{polylog}(n)$. Prior to our result, a bound of $\tilde{O}(D)$ is known only when $\kappa=1,2$ [Parter, Petruschka DISC'22]. For $\kappa\geq 3$, this bound can be obtained only by an $O(\log n)$-approximation algorithm [Censor-Hillel, Ghaffari, Kuhn PODC'14], and the only known exact algorithm takes $O\left((\kappa\Delta D)^{O(\kappa)}\right)$ rounds, where $\Delta$ is the maximum degree [Parter DISC'19]. Our result answers an open problem by Nanongkai, Saranurak, and Yingchareonthawornchai [STOC'19].

We consider the classical contention resolution problem where nodes arrive over time, each with a message to send. In each synchronous slot, each node can send or remain idle. If in a slot one node sends alone, it succeeds; otherwise, if multiple nodes send simultaneously, messages collide and none succeeds. Nodes can differentiate collision and silence only if collision detection is available. Ideally, a contention resolution algorithm should satisfy three criteria: low time complexity (or high throughput); low energy complexity, meaning each node does not make too many broadcast attempts; strong robustness, meaning the algorithm can maintain good performance even if slots can be jammed. Previous work has shown, with collision detection, there are "perfect" contention resolution algorithms satisfying all three criteria. On the other hand, without collision detection, it was not until 2020 that an algorithm was discovered which can achieve optimal time complexity and low energy cost, assuming there is no jamming. More recently, the trade-off between throughput and robustness was studied. However, an intriguing and important question remains unknown: without collision detection, are there robust algorithms achieving both low total time complexity and low per-node energy cost? In this paper, we answer the above question affirmatively. Specifically, we develop a new randomized algorithm for robust contention resolution without collision detection. Lower bounds show that it has both optimal time and energy complexity. If all nodes start execution simultaneously, we design another algorithm that is even faster, with similar energy complexity as the first algorithm. The separation on time complexity suggests for robust contention resolution without collision detection, ``batch'' instances (nodes start simultaneously) are inherently easier than ``scattered'' ones (nodes arrive over time).

In this paper, we consider contention resolution on a multiple-access communication channel. In this problem, a set of nodes arrive over time, each with a message it intends to send. In each time slot, each node may attempt to broadcast its message or remain idle. If a single node broadcasts in a slot, the message is received by all nodes; otherwise, if multiple nodes broadcast simultaneously, a collision occurs and none succeeds. If collision detection is available, nodes can differentiate collision and silence (i.e., no nodes broadcast). Performance of contention resolution algorithms is often measured by throughput -- the number of successful transmissions within a period of time; whereas robustness is often measured by jamming resistance -- a jammed slot always generates a collision. Previous work has shown, with collision detection, optimal constant throughput can be attained, even if a constant fraction of all slots are jammed. The situation when collision detection is not available, however, remains unclear. In a recent breakthrough paper [Bender et al., STOC '20], a crucial case is resolved: constant throughput is possible without collision detection, but only if there is no jamming. Nonetheless, the exact trade-off between the best possible throughput and the severity of jamming remains unknown. In this paper, we address this open question. Specifically, for any level of jamming ranging from none to constant fraction, we prove an upper bound on the best possible throughput, along with an algorithm attaining that bound. An immediate and interesting implication of our result is, when a constant fraction of all slots are jammed, which is the worst-case scenario, there still exists an algorithm achieving a decent throughput: $\Theta(t/\log{t})$ messages could be successfully transmitted within $t$ slots.