Distributed Graph Coloring
Elkin, Michael / Barenboim, Leonid The focus of this monograph is on symmetry breaking problems in the message-passing model of distributed computing. In this model a communication network is represented by a n-vertex graph G = (V, E), whose vertices host autonomous processors. The processors communicate over the edges of G in discrete rounds. The goal is to devise algorithms that use as few rounds as possible.
A typical symmetry-breaking problem is the problem of graph colori...