Overcoming Congestion in Distributed Coloring

Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm…