We obtain better algorithms for computing more balanced orientations and degree splits in Local. Important to our result is a connection to the hypergraph sinkless orientation problem [9, SODA'25]. We design an algorithm of complexity O(ϵ-1 · log n) for computing a balanced orientation with discrepancy at most ϵ · deg(v) for every vertex v ∈ V. This improves upon a previous result by [16, Distrib. Comput. 2020] of complexity O(ϵ-1 · log ϵ-1 · (log log ϵ-1)1.71 •log n). Further, we show that this result can also be extended to compute undirected degree splits with the same discrepancy and in the same runtime.

As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any n-node graph with maximum degree Δ with (1+ε)Δ+O(log⁡n) colors in Õ(log2.5 n + log2 Δ log n) rounds. This brings the upper bound polynomially close to the lower bound of Ω(log n/log log n) rounds that also holds in the more powerful LOCAL model [Chang, He, Li, Pettie, Uitto; SODA'l8]. As long as Δ≥clog⁡n our algorithm uses fewer than 2Δ - 1 colors and to the best of our knowledge is the first polylogarithmic-round CONGEST algorithm achieving this for any range of Δ.

In contrast to the $$(\varDelta +1)$$ -vertex coloring problem, the $$\varDelta $$ -vertex coloring problem cannot be solved with a simple sequential greedy algorithm. As a result it has become one of the prototypical problems for understanding the complexity of non-greedy distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS’16]. Despite recent progress in the design of efficient $$\varDelta $$ -coloring algorithms, we lack an asymptotically optimal algorithm. In this work we present a $$O(\log n)$$ -round deterministic $$\varDelta $$ -coloring algorithm for locally dense constant-degree graphs, matching the lower bound for the problem on general graphs. For general $$\varDelta $$ the algorithms’ complexity is $$\min \{\widetilde{O}(\log ^{5/3}n),O(\varDelta +\log n)\}$$ . Almost all recent distributed and sublinear graph coloring algorithms (also for coloring with more than $$\varDelta $$ colors) decompose the graph into sparse and dense parts. Our algorithm works for the case that this decomposition has no sparse vertices. Ironically, in recent (randomized) $$\varDelta $$ -coloring algorithms, dealing with sparse parts was relatively easy and these dense parts arguably posed the major hurdle. We present a solution that addresses the dense parts and may have the potential for extension to sparse parts. Our approach is fundamentally different from prior deterministic algorithms and hence hopefully contributes towards designing an optimal algorithm for the general case, and potentially also for other non-greedy problems. Additionally, we leverage our result to also obtain a randomized $$\min \{\widetilde{O}(\log ^{5/3}\log n), O(\varDelta +\log \log n)\}$$ -round algorithm for $$\varDelta $$ -coloring locally dense graphs that also matches the lower bound for the problem on general constant-degree graphs [Brandt et al.; STOC’16].

We give new, improved bounds for approximating the sparsest cut value or in other words the conductance $$\phi $$ of a graph in the $$\textsf{CONGEST}$$ model. As our main result, we present an algorithm running in $$O(\log ^2 n/\phi )$$ rounds in which every vertex outputs a value $$\tilde{\phi }$$ satisfying $$\phi \le \tilde{\phi }\le \sqrt{2.01\phi }$$ . In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix $$L:=I-{{\,\textrm{Deg}\,}}^{-1/2}A{{\,\textrm{Deg}\,}}^ {-1/2}$$ , where, A is the adjacency matrix and $${{\,\textrm{Deg}\,}}$$ is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model. The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the $$\textsf{CONGEST}$$ model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs. Full version: https://arxiv.org/abs/2508.19898 .

We analyse simple distributed colouring algorithms on hyperbolic random graphs (HRGs), a generative model capturing properties of real-world networks such as power-law degrees and large clustering. We focus on the number of rounds and the colour space needed to colour HRGs in the distributed setting.

In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs:

Publisher Copyright: © 2026 Copyright held by the owner/author(s).

We study the epigenetic consensus problem, in which simple processors move across and modify a shared memory, seeking to achieve consensus across the cells of the memory. The memory topology is a ring with the cells initialised to 0 or 1. The ring is traversed by multiple processors moving clockwise in synchronous steps. Each processor belongs to one of four types: There are two types of erasers that erase either memory cells holding a 0 adjacent to a 1 or those holding a 1 adjacent to a 0. There are also two types of writers; those writing 1 or those writing 0 into empty cells.We are interested whether and how fast the above process converges to a consensus state where all memory cells have the same value. The origin of this process lies in biology, in the modelling of the activation and deactivation of DNA sequences. A variant of this process has been introduced and studied by Rashid, Taubenfeld, and Bar-Joseph.The convergence properties of the process depend on the initialisation of the shared memory, as well as on the number and types of processors and their initial locations. We show that, with adversarial initial processor positions, consensus cannot be reached.Having observed that a deterministic or adversarial model can be very powerful with regards to reaching consensus, we focus our attention on randomised initialisations. As our main contribution, we show the following two results that depend on a measure of processor bias describing whether the processors are biased towards increasing 0s or 1s in the cells: (a) With randomised initialisation of the memory cells and random processor placement, eventually consensus is reached with high probability, even with sublinear processor bias. (b) With high probability, consensus is reached quickly whenever there is an arbitrarily small constant factor processor bias. These two results hold even if the memory cell initialisation has a bias that is in the opposite direction compared to the bias in the processors.

Given a graph G = (V, E), a β-ruling set is a subset S ⊆ V that is i) independent, and ii) every node υ ∈ V has a node of S within distance β. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an O(log log n)-round randomized algorithm for computing 2-ruling sets on trees, almost matching the Ω (log log n/log log log n) lower bound given by Balliu et al. [FOCS'20]. Second, we show that 2-ruling sets can be solved in Õ(log5/3 log n) rounds in high-girth graphs. Lastly, we show that O(log log log n)-ruling sets can be computed in Õ(log log n) rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance β.

The Δ-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS'16]. Despite recent progress in the design of efficient Δ-coloring algorithms, there is currently a polynomial gap between the upper and lower bounds.

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems.

Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from (2/√3) to 4/3 depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.

There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while (2Δ-1)-edge coloring - where Δ is the maximum degree - can be solved in 𝒪(log^{∗}(n)) rounds on constant-degree graphs, the seemingly minor reduction to (2Δ-2) colors leads to an Ω(log n) lower bound [Chang, He, Li, Pettie & Uitto, SODA'18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed 𝒪(log n)-round reduction from the (2Δ-2)-edge coloring problem to the much easier (2Δ-1)-edge coloring problem. This reduction is optimal, as the (2Δ-2)-edge coloring problem admits an Ω(log n) lower bound that even holds on the class of constant-degree graphs, whereas the 2Δ-1-edge coloring problem can be solved in 𝒪(log^{∗}n) rounds. By plugging in the (2Δ-1)-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in 𝒪(log^{12}Δ + log^{∗} n) rounds, we obtain an optimal runtime of 𝒪(log n) rounds as long as Δ = 2^{𝒪(log^{1/12} n)}. Previously, such an optimal algorithm was only known for the class of constant-degree graphs [Brandt, Maus, Narayanan, Schager & Uitto, SODA'25]. Furthermore, on general graphs our reduction improves the runtime from 𝒪̃(log³ n) to 𝒪̃(log^{5/3} n). In addition, we also obtain an optimal 𝒪(log log n)-round randomized reduction of (2Δ - 2)-edge coloring to (2Δ - 1)-edge coloring. This leads to a 𝒪̃(log^{5/3} log n)-round (2Δ-2)-edge coloring algorithm, which beats the (very recent) previous state-of-the-art taking 𝒪̃(log^{8/3}log n) rounds from [Bourreau, Brandt & Nolin, STOC'25]. Lastly, we obtain an 𝒪(log_Δ n)-round reduction from the (2Δ-1)-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem.

Abstract Locally Checkable Labeling () problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and colorings. A successful line of research has been studying the complexities of s on paths/cycles, trees, and general graphs, providing many interesting results for the model of distributed computing. In this work, we initiate the study of problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an problem in the model, automatically provides an exponentially faster algorithm for the low-space setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the setting are obtained through lower bounds for problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests this is not possible, hence using optimal memory requires new solutions.

Abstract In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph $$G^k$$ G k , where each node of the communication network G is connected to all of its k-hop neighbors. A $$\beta $$ β -ruling set is a set of non-adjacent nodes such that each node in G has a ruling neighbor within $$\beta $$ β hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM’16, Ghaffari SODA’19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of $$G^k$$ G k in essentially the same time as they can be computed in G. Our main contribution is a deterministic $${{\,\textrm{poly}\,}}(k,\log n)$$ poly ( k , log n ) time algorithm for computing k-ruling sets of $$G^k$$ G k , which (for k > 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. We also revisit the shattering algorithm for MIS [BEPS JACM’16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA’16].

Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures the central challenges in data center computations. Chang et al. [PODC'2019] gave an extremely fast, constant time, algorithm for the (Δ+1)-coloring problem, where Δ is the maximum degree of an input graph of n nodes. The algorithm works in the most restrictive low-space setting, where each machine has nδ local space for a constant 0 < δ < 1.

We consider the problem of coloring graphs of maximum degree $Δ$ with $Δ$ colors in the distributed setting with limited bandwidth. Specifically, we give a $\mathsf{poly}\log\log n$-round randomized algorithm in the CONGEST model. This is close to the lower bound of $Ω(\log \log n)$ rounds from [Brandt et al., STOC '16], which holds also in the more powerful LOCAL model. The core of our algorithm is a reduction to several special instances of the constructive Lovász local lemma (LLL) and the $deg+1$-list coloring problem.

In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph Gk, where each node of the communication network G is connected to all of its k-hop neighbors.

We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent breakthrough result by Coy and Czumaj [STOC'22] shows that, in this setting, it is possible to deterministically identify connected components on graphs in O (log D + log log n) rounds, where D is the diameter of the graph and n the number of nodes. The authors left open a major question: is it possible to get rid of the additive log log n factor and deterministically identify connected components in a runtime that is completely independent of n?

We give a randomized Δ-coloring algorithm in the LOCAL model that runs in poly log log n rounds, where n is the number of nodes of the input graph and Δ is its maximum degree. This means that randomized Δ-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, poly log log n, given the known Ω(logΔ logn) lower bound [Brandt et al., STOC '16].

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ < 1. Here D is the diameter of the tree and n is the number of nodes---we emphasize that our running time is independent of n.

We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log*n) rounds in forests (with high probability) and 2O(log*n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm.

We show the first conditionally optimal deterministic algorithm for $3$-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log \log n)$ rounds and uses optimal global space. The best previous algorithm requires $4$ colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an $O(\log \log n)$-round algorithm to compute a partition of the forest into $O(\log n)$ ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.

Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes $\{\mathsf{cycles, trees, forests, chordal, cactus, even\text{-}hole\text{-}free, claw\text{-}free}\}$, there are schedules that use $O(\varepsilon^{-1})$ batches and incur only a $1+\varepsilon$ multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in $O(\varepsilon^{-1}\log^* n)$ distributed time, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.

We present ${\rm poly\log\log n}$-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into $k$ parts such that a node of degree $d(u)$ has $\approx d(u)/k$ neighbors in each part. Our techniques can be seen as the first progress towards general ${\rm poly\log\log n}$-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized ${\rm poly\log\log n}$-round CONGEST algorithm for $(1+ε)Δ$-edge coloring $n$-node graphs of sufficiently large constant maximum degree $Δ$, for any $ε>0$. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

Abstract Linial’s famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree $$\varDelta $$ Δ to an $$O(\varDelta ^2\log m)$$ O ( Δ 2 log m ) -coloring, in a single round in the LOCAL model. We give a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m-coloring in a directed graph of maximum outdegree $$\beta $$ β , if every node has a list of size $$\varOmega (\beta ^2 (\log \beta +\log \log m + \log \log |{\mathcal {C}}|))$$ Ω ( β 2 ( log β + log log m + log log | C | ) ) from a color space $${\mathcal {C}}$$ C then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial’s color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $$({\text {deg}}+1)$$ ( deg + 1 ) -list coloring algorithm from Barenboim et al. (PODC, pp 437–446, 2018) by slightly reducing the runtime to $$O(\sqrt{\varDelta \log \varDelta })+\log ^* n$$ O ( Δ log Δ ) + log ∗ n and significantly reducing the message size (from $$\varDelta ^{O(\log ^* \varDelta )}$$ Δ O ( log ∗ Δ ) to roughly $$\varDelta $$ Δ ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. (in: FOCS, pp 625–634, 2016).

In this paper we present a deterministic CONGEST algorithm to compute an O(kΔ)-vertex coloring in O(Δ/k)+łog^* n rounds, where Δ is the maximum degree of the network graph and 1łeq kłeq O(Δ) can be freely chosen. The algorithm is extremely simple: Each node locally computes a sequence of colors and then it "tries colors" from the sequence in batches of size k. Our algorithm subsumes many important results in the history of distributed graph coloring as special cases, including Linial's color reduction [Linial, FOCS'87], the celebrated locally iterative algorithm from [Barenboim, Elkin, Goldenberg, PODC'18], and various algorithms to compute defective and arbdefective colorings. Our algorithm can smoothly scale between these and also simplifies the state of the art (Δ+1)-coloring algorithm. At the cost of losing the full algorithm's simplicity we also provide a O(kΔ)-coloring algorithm in O(√Δ/k )+łog^* n rounds. We also provide improved deterministic algorithms for ruling sets, and, additionally, we provide a tight characterization for one-round color reduction algorithms.

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n-node graph G, and where the nodes of G operate in synchronous communication rounds in which they can exchange O(logn)-bit messages over all the edges of G. For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O(log5logn) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O(logΔ + log6logn) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O(logn), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

We present a poly $\log \log n$ time randomized CONGEST algorithm for a natural class of Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between $\log n$ and poly $\log \log n$. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhon and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhon [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers.

Abstract We present a randomized distributed algorithm that computes a $$\Delta $$ Δ -coloring in any non-complete graph with maximum degree $$\Delta \ge 4$$ Δ ≥ 4 in $$O(\log \Delta ) + 2^{O(\sqrt{\log \log n})}$$ O ( log Δ ) + 2 O ( log log n ) rounds, as well as a randomized algorithm that computes a $$\Delta $$ Δ -coloring in $$O((\log \log n)^2)$$ O ( ( log log n ) 2 ) rounds when $$\Delta \in [3, O(1)]$$ Δ ∈ [ 3 , O ( 1 ) ] . Both these algorithms improve on an $$O(\log ^3 n / \log \Delta )$$ O ( log 3 n / log Δ ) -round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $$\Omega (\log \log n)$$ Ω ( log log n ) round lower bound of Brandt et al. (STOC’16).

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

We show that the (degree + 1)-list coloring problem can be solved deterministically in O(D · log n · log2 Δ) rounds in the CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [49], this implies the first efficient (i.e., poly log n-time) deterministic CONGEST algorithm for the (Δ + 1)-coloring and the (degree + 1)-list coloring problem. Previously the best known algorithm required [EQUATION] rounds and was not based on network decompositions.

We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G2. While we focus mostly on exploring this theme in the distributed CONGEST model, we also show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on G2 would be quite difficult to solve efficiently on G, due to congestion. However, we show that the picture is both more complicated and more interesting.

We give efficient randomized and deterministic distributed algorithms for computing a distance-2 vertex coloring of a graph G in the CONGEST model. In particular, if Δ is the maximum degree of G, we show that there is a randomized CONGEST model algorithm to compute a distance-2 coloring of G with Δ2 + 1 colors in O(log Δ · log n) rounds. Further if the number of colors is slightly increased to (1 + ∈)Δ2 for some ∈ > 1/polylog n, we show that it is even possible to compute a distance-2 coloring deterministically in polylog n time in the CONGEST model. Finally, we give a O(Δ2 + log* n)-round deterministic CONGEST algorithm to compute distance-2 coloring with Δ2 + 1 colors.

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: $O(1)$, $Θ(\log n)$, $Θ(n)$, or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity $Θ(\log^* n)$, and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.

We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.

Linial's famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Δ$ to a $O(Δ^2\log m)$-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an $m$-coloring in a directed graph of maximum outdegree $β$, if every node has a list of size $Ω(β^2 (\log β+\log\log m + \log \log |\mathcal{C}|))$ from a color space $\mathcal{C}$ then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial's color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $(deg+1)$-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to $O(\sqrt{Δ\logΔ})+\log^* n$ and significantly reducing the message size (from huge to roughly $Δ$). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16].

We study a process of \emph{averaging} in a distributed system with \emph{noisy communication}. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value $v$, the receiving agent receives $v+N$, where $N$ is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares $TSS(t)$, which measures the sum of square distances from the average load to the \emph{initial average} and (ii) $\barϕ(t)$, measures the sum of square distances from the average load to the \emph{running average} (average at time $t$). It is known that the simple averaging protocol---in which an agent sends its current value and sets its new value to the average of the received value and its current value---converges eventually to a state where $\barϕ(t)$ is small. It has been observed that $TSS(t)$, due to the noise, eventually diverges and previous research---mostly in control theory---has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of $\barϕ(t)$ and precise bounds on the drift of $TSS(t)$ that show that albeit $TSS(t)$ eventually diverges, for a wide and interesting range of parameters, $TSS(t)$ stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding.

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(logn) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective `old` neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds.

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly log n-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G=(V,E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly log n-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results:

The Lovász Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most p and depends on at most d other events, there is an assignment of the variables that avoids all bad events if the LLL criterion ep(d+1)<1 is satisfied. Nowadays, in the area of distributed graph algorithms it has also become a powerful framework for developing---mostly randomized---algorithms. A classic result by Moser and Tardos yields an O(log^2 n) algorithm for the distributed Lovász Local Lemma [JACM'10] if ep(d + 1) < 1 is satisfied. Given a stronger criterion, i.e., demanding a smaller error probability, it is conceivable that we can find better algorithms. Indeed, for example Chung, Pettie and Su [PODC'14] gave an O(log_epd^2 n) algorithm under the epd^2 < 1 criterion. Going further, Ghaffari, Harris and Kuhn introduced an 2^O(√log log n ) time algorithm given d^8 p = O(1) [FOCS'18]. On the negative side, Brandt et al.\ and Chang et al.\ showed that we cannot go below Ω(log log n) (randomized) [STOC'16] and Ω(log n) (deterministic) [FOCS'16], respectively, under the criterion pleq 2^-d . Furthermore, there is a lower bound of Ω(log^* n) that holds for any criterion. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at p = 2^-d : we provide a simple deterministic (!) algorithm that matches the Ω(log^* n) lower bound in bounded degree graphs, if p < 2^-d , whereas for p \geq 2^-d , the Ωmega(log log n) randomized and the Ω(log n) deterministic lower bounds hold. In many applications variables affect more than two events; our main contribution is to extend our algorithm to the case where random variables influence at most three different bad events. We show that, surprisingly, the sharp threshold occurs at the exact same spot, providing evidence for our conjecture that this phenomenon always occurs at p = 2^-d , independent of the number r of events that are affected by a variable. Almost all steps of the proof framework we provide for the case r=3 extend directly to the case of arbitrary r; consequently, our approach serves as a step towards characterizing the complexity of the LLL under different exponential criteria.

We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For ε 1/ poly log Δ we obtain two algorithms with approximation factor (1 + ε)(1 + ł n (Δ + 1)) and with runtimes 2O(√ log n log log n) and O(Δ poly log Δ + poly log Δ log* n), respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic O(log Δ)-approximation algorithm for the minimum connected dominating set with time complexity 2O(√ log n log log n).

We prove that the maximum independent set approximation problem with polylogarithmic approximation factor is P-SLOCAL-complete.

We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1+o(1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(logn). For smaller Δ, we give a polylogarithmic-time 3Δ/2-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors, and they improve significantly on the recent polylogarithmic-time (2Δ−1)(1+o(1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2Δ−1)-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. We require two properties from our algorithms: (1) They should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and they coincide with the definition of the static graph problem if no topological change appeared recently. (2) If a constant neighborhood around some part of the graph is stable during an interval, the algorithms quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph, namely (degree+1)-vertex coloring and maximal independent set (MIS).

The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length Θ(log log n), where our bound is tight including the leading constant. Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps.

This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2O(√logn). Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms.

The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.