Overview
The state of the art in distributed symmetry breaking
A curated database of algorithms and lower bounds for six fundamental problems in distributed graph algorithms, in the LOCAL and CONGEST models, deterministic and randomized. For every range of the maximum degree Δ, the atlas highlights which results are the state of the art.
Many results follow from others through reductions, for example a maximal matching from an MIS of the line graph; the tables show them next to the results they are derived from. The bibliography lists every paper the atlas draws on.
The data is open: every entry is a file in the GitHub repository, licensed under CC BY 4.0. Missing a result or found a mistake? Use the Report an issue button next to any result or paper.