By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in $o(\log n)$ rounds, we can speed it up to $O(\log^*n)$ rounds, and if we have a randomized $O(\log^*n)$ rounds algorithm, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity $Θ(\log\log n)$ and deterministic complexity $Θ(\log n)$. However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem $Π$ such that the round complexity of $Π$ is $Ω(\sqrt n)$ in the usual randomized \local model with private randomness, but if the nodes have access to a source of shared randomness, then the complexity drops to $O(\log n)$. As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem $Π$ demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem $Π$ also gives a separation between finitely dependent distributions and non-signaling distributions.

We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as (Δ + 1)-coloring and maximal independent set. It is known from previous work that, in n-node graphs of maximum degree Δ, any problem in the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity O (log Δ + log* n).

International audience

We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2022]. We focus on the vertex coloring problem, and our contributions concern both lower and upper bounds for this problem. On the upper bound side, we design an algorithm tolerating an arbitrarily large number of crash failures that computes an $O(Δ^2)$-coloring of any $n$-node graph of maximum degree $Δ$, in $O(\log^\star n)$ rounds. This extends Linial's seminal result from the (synchronous failure-free) LOCAL model to its asynchronous crash-prone variant. Then, by allowing a dependency on $Δ$ on the runtime, we show that we can reduce the colors to $\big(\frac12(Δ+1)(Δ+2)-1 \big)$. For cycles (i.e., for $Δ=2$), our algorithm achieves a 5-coloring of any $n$-node cycle, in $O(\log^\star n)$ rounds. This improves the known 6-coloring algorithm by Fraigniaud et al., and fixes a bug in their algorithm, which was erroneously claimed to produce a 5-coloring. On the lower bound side, we show that, for $k<5$, and for every prime integer~$n$, no algorithm can $k$-color the $n$-node cycle in the asynchronous crash-prone variant of LOCAL, independently from the round-complexities of the algorithms. This lower bound is obtained by reduction from an original extension of the impossibility of solving weak symmetry-breaking in the wait-free shared-memory model. We show that this impossibility still holds even if the processes are provided with inputs susceptible to help breaking symmetry.

We present a wait-free algorithm for proper coloring the n ≥ 3 nodes of the asynchronous cycle Cn, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n and uses up to five colors, and each node terminates upon completing at most O(log*n) write-read-compute steps.

We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle C_n, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n ≥ 3, and runs in O(log^*n) rounds in C_n. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely {0,…,4}, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever n is a power of a prime. Indeed, our model coincides with the shared-memory model whenever n = 3, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.

One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O ( Δ + log * n ) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o (log * n ) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1-1/ n requires Ω (min { Δ , log log n / log log log n }) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω (min { Δ , log n / log log n }) rounds; this is an improvement over prior lower bounds also as a function of n .

We investigate a distributed maximal independent set reconfiguration problem , in which there are two MIS for which every node is given its membership status, and the nodes need to communicate with their neighbors to find a reconfiguration schedule from the first MIS to the second. We forbid two neighbors to change their membership status at the same step. We provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O ( MIS + R32 ) rounds. For bounded degree graphs, this is O ( log ⁎ ⁡ n ) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Δ + log log n / log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Δ + log n / log log n) rounds; this is an improvement over prior lower bounds also as a function of n.

Consider a computer network that consists of a path with n nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a constant-sized set subject to some local constraints---more formally, we have an LCL (locally checkable labeling) problem. How many communication rounds are needed (in the standard LOCAL model of computing) to solve this problem?

Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.

Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.

This work provides an analysis of checkpointing strategies for minimizing expected job execution times in an environment that is subject to processor failures. In the case of both sequential and parallel jobs, we give the optimal solution for exponentially distributed failure inter-arrival times, which, to the best of our knowledge, is the first rigorous proof that periodic checkpointing is optimal. For non-exponentially distributed failures, we develop a dynamic programming algorithm to maximize the amount of work completed before the next failure, which provides a good heuristic for minimizing the expected execution time. Our work considers various models of job parallelism and of parallel checkpointing overhead. We first perform extensive simulation experiments assuming that failures follow Exponential or Weibull distributions, the latter being more representative of real-world systems. The obtained results not only corroborate our theoretical findings, but also show that our dynamic programming algorithm significantly outperforms previously proposed solutions in the case of Weibull failures. We then discuss results from simulation experiments that use failure logs from production clusters. These results confirm that our dynamic programming algorithm significantly outperforms existing solutions for real-world clusters.