Browse Books

Reviewer: Krishnaiyan Thulasiraman

Distributed computing has been an active area of research for a few decades now; we have witnessed significant advances in the principles of distributed computing and the design and analysis of distributed algorithms. Now is the right time for the publication of monographs focused on advances in specific areas of distributed computing. This book is a welcome addition to such a series. It is mainly concerned with two problems: graph coloring and maximal independent sets. These problems are called symmetry breaking problems. Chapter 1 gives a brief introduction to the message-processing model of distributed computing. All of the algorithms discussed in this book use this model. Also, all of the algorithms considered are synchronous algorithms. Chapter 2 covers several basic results in graph coloring that will be of interest to the discussions in later chapters. In chapter 3, the authors discuss several distributed graph coloring algorithms. The focus is on Δ+1 coloring. Here Δ is the maximum degree in the graph. First, a fundamental color reduction technique is presented. This enables one to reduce a given coloring to Δ+1 coloring in a certain number of rounds. The other main topics covered include the Cole-Vishkin algorithm for three-coloring oriented trees; extensions to coloring graphs with bounded maximum degree; further extension by Goldberg, Plotkin, and Shannon to Δ+1 coloring of an n -vertex graph in O (Δ2) + log* n time; a new color reduction technique more efficient than the one presented earlier in this chapter; and Linial's algorithm for O (Δ2) coloring in log* n + O (1) rounds. Chapter 4 discusses certain lower bound results. The authors develop a procedure to decompose a graph into a certain number (a function of arboricity denoted by a ) of forests in chapter 5. An algorithm that uses this decomposition for 3 O(a) coloring with running time O (log n ) time is then presented. The issue of tradeoff between the number of colors and the number of rounds (equivalently, time) is then considered. The authors provide an algorithm to achieve O ( a ) coloring in O ( a log n ). Extensions to maximum independent set (MIS) constructions are also given. Defective coloring algorithms that lead to a Δ+1 coloring of an n -vertex graph in O (Δ) + log* n time are covered in chapter 6. Chapter 7 introduces arbdefective coloring, which partitions a graph into subgraphs of bounded arboricity. Using this, the authors present a result that answers in the affirmative the question, raised by Linial, of whether one can determine in polylogarithmic time a coloring with significantly fewer than Δ2 colors. From the vertex coloring of the line graph of a graph G , one can get an edge coloring of G . So all vertex coloring algorithms discussed thus far can be used for computing edge coloring. Combining forest decomposition with the Cole-Vishkin three-vertex coloring algorithm for oriented trees, chapter 8 presents Panconesi and Rizzi's 2Δ-1 coloring algorithm for general graphs that runs in O (Δ) + log* n time. The authors' work on edge coloring for graphs with bounded neighborhood independence is then discussed. Since the line graph of a graph has neighborhood independence bounded by 2, one can get an O (Δ1+ e ) edge coloring algorithm that runs in O (log* n log Δ) time. Chapter 9 introduces the network decomposition technique originally invented by Awerbuch, Goldberg, Luby, and Plotkin for solving symmetry breaking problems. The main result is that, by using network decomposition, one can get a distributed maximal independent set (MIS) and Δ+1 coloring of time complexity 2 O (√log n ), a result due to Panconesi and Srinivasan. Chapter 10 gives an introduction to distributed randomized algorithms for MIS and vertex coloring problems. An algorithm of complexity O (log n ) that achieves a Δ+1 coloring with high probability is discussed. Also, it is shown that O (Δ) coloring can be achieved in O (√log n ) time with probability 1-1/ n c for an arbitrarily large constant c . Chapter 11 concludes with some open problems. Two minor comments: an introductory discussion of symmetry breaking and what it is all about is absent, as is the context or a scenario in which one encounters the need for synchronous distributed algorithms for the coloring problem. The authors have succeeded in their goal of reporting most of the advances in distributed graph coloring that have occurred since the publication of Peleg's book [1]. The writing style is very good, smoothly transitioning from one development to the next. The book is suitable for an advanced course in distributed algorithms for students in theoretical computer science. Also, portions of the book can be used to supplement a course in advanced graph theory and algorithms. Online Computing Reviews Service