Michael Elkin: Distributed Graph Coloring and Other Symmetry Breaking Problems

Consider an unweighted undirected graph G, and suppose that each vertex hosts a processor. The processors communicate over edges of G. Suppose also that the communication is synchronous, i.e., it proceeds in discrete rounds. On each round each vertex is allowed to send messages to all its neighbors. How many rounds are needed to color the graph G legally in (Delta+1) colors, where Delta is the maximum degree of the graph G? How many rounds are needed to compute a maximal (under containment) independent set, or a maximal matching?

These are classical questions in distributed computing. Efficient randomized algorithms for these problems were devised more than twenty years ago. On the other hand, efficient deterministic algorithms turned out to be far more elusive. Recently significant progress was achieved in devising such algorithms, but still many central questions remain wide open. Major progress was also achieved in devising randomized algorithms. In this talk I will survey this area, discuss recent results and main open problems.