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 coloring. Denote by ? the maximum degree of G. While coloring G with ? + 1 colors is trivial in the centralized setting, the problem becomes much more challenging in the distributed one. One can also compromise on the number of colors, if this allows for more efficient algorithms. Other typical symmetry-breaking problems are the problems of computing a maximal independent set (MIS) and a maximal matching (MM). The study of these problems dates back to the very early days of distributed computing. The founding fathers of distributed computing laid firm foundations for the area of distributed symmetry breaking already in the eighties. In particular, they showed that all these problems can be solved in randomized logarithmic time. Also, Linial showed that an O(?2)-coloring can be solved very efficiently deterministically.
However, fundamental questions were left open for decades. In particular, it is not known if the MIS or the (? + 1)-coloring can be solved in deterministic polylogarithmic time. Moreover, until recently it was not known if in deterministic polylogarithmic time one can color a graph with significantly fewer than ?2 colors. Additionally, it was open (and still open to some extent) if one can have sublogarithmic randomized algorithms for the symmetry breaking problems.
Recently, significant progress was achieved in the study of these questions. More efficient deterministic and randomized (? + 1)-coloring algorithms were achieved. Deterministic ?1 + o(1)-coloring algorithms with polylogarithmic running time were devised. Improved (and often sublogarithmic-time) randomized algorithms were devised. Drastically improved lower bounds were given. Wide families of graphs in which these problems are solvable much faster than on general graphs were identified.
The objective of our monograph is to cover most of these developments, and as a result to provide a treatise on theoretical foundations of distributed symmetry breaking in the message-passing model. We hope that our monograph will stimulate further progress in this exciting area.
Table of Contents
Basics of Graph Theory
Basic Distributed Graph Coloring Algorithns
Forest-Decomposition Algorithms and Applications
Edge-Coloring and Maximal Matching
Introduction to Distributed Randomized Algorithms
Conclusion and Open Questions
About the Author(s)Leonid Barenboim
, Ben-Gurion University of the Negev, Israel Michael Elkin
, Ben-Gurion University of the Negev, Israel
This book is a monograph on so-called symmetry breaking problems of distributed computing. In particular, distributed algorithms for the graph coloring and maximal independent set problems are studied in detail…The beginning of the book contains a whole chapter on those basic results in graph theory that are most relevant for distributed algorithms. Classical theorems on coloring, planar graphs, arboricity, etc., are discussed. In the following chapters the authors consider several results and methods for soling deterministic symmetry breaking problems, both old and recent ones…A chapter is devoted to randomized distributed algorithms. Recent and very effective (sometimes running in sublogarithmic time) algorithms are discussed for coloring, the maximal independent set and the maximal matching problems. The book ends with a chapter including several open problems in this beautiful area…The authors cover a large portion of the most recent developments in symmetry breaking problems in the message-passing model, providing algorithms and their proofs. An interested reader can learn many important results and techniques in this field. Moreover, the book is suitable for teaching a graduate course.Bela Csaba