The Taub Faculty of Computer Science Events and Talks

In a distributed message passing model a communication network is represented by an n-vertex graph whose vertices host processors, and edges serve as communication links. One of the most fundamental goals in this setting is breaking the symmetry in the network. Specifically, the tasks of computing vertex coloring, maximal matching, and maximal independent set are of great importance. In the mid-eighties several randomized distributed algorithms for these problems were devised. [Luby 86, Alon, Babai and Itai 86, Israeli and Itai 86]. These algorithms require O(log n) rounds, and until recently they remained the best-known ones. We present significantly improved results for these problems. These results include: 1. A randomized algorithm for computing a maximal matching in O(log Delta+ (log log n)^4) rounds, where Delta is the maximum degree in the graph. This result is provably optimal for all log Delta in the range [(log log n)^4 , \sqrt {log n}]. 2. A randomized maximal independent set algorithm requiring O(log Delta \sqrt{ log n}) rounds. 3. A randomized (Delta+1)-coloring algorithm requiring O(log Delta + \exp{ \sqrt {\log \log n}}) rounds.

We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Low arboricity graphs include planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that excludes any fixed minor, and many other graphs. These graphs may have unbounded maximum degree. Nevertheless, for low arboricity graphs we obtain a maximal matching algorithm that runs in O(\sqrt {log n}) time, and a maximal independent set algorithm that runs in O(log^{3/4} n) time.

The talk is based on a joint work with Michael Elkin, Seth Pettie, and Johannes Schneider.