Abstract The Maximal Independent Set (MIS) problem is one of the basics in the study of
locality in distributed graph algorithms. This paper presents a very simple randomized …

Symmetry-breaking problems are among the most well studied in the field of distributed
computing and yet the most fundamental questions about their complexity remain open. In …

The gap between the known randomized and deterministic local distributed algorithms
underlies arguably the most fundamental and central open question in distributed graph …

We present a simple deterministic distributed algorithm that computes a (Δ+1)-vertex
coloring in O(log^2Δ.log\n) rounds. The algorithm can be implemented with O(log\n)-bit …

The (∆+ 1)-coloring problem is a fundamental symmetry breaking problem in distributed
computing. We give a new randomized coloring algorithm for (∆+ 1)-coloring running in O …

Locally Checkable Labeling (LCL) problems include essentially all the classic problems of
$\mathsf {LOCAL} $ distributed algorithms. In a recent enlightening revelation, Chang and …

The main result of this paper is a simulation algorithm which, under quite general
constraints, transforms algorithms running in the Congested Clique model into algorithms …

We prove several new tight or near-tight distributed lower bounds for classic symmetry
breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any …

Given a graph G=(V,E), an (α,β)-ruling set is a subset S⊆V such that the distance between
any two vertices in S is at least α, and the distance between any vertex in V and the closest …

In this article, we present a deterministic algorithm to compute an O (k Δ)-vertex coloring in O
(Δ/k)+ log* n rounds, where Δ is the maximum degree of the network graph and k≥ 1 can be …