Chapter 8

In Chapter 1, we looked at distributed algorithms for coloring. In particular, we saw that rings and rooted trees can be colored with 3 colors in log ∗ n+O(1) rounds. In this chapter, we will reconsider the distributed coloring problem. We will look at a classic lower bound that shows that the result of Chapter 1 is tight: Coloring rings (and rooted trees) indeed requires Ω(log ∗ n) rounds. In particular, we will prove a lower bound for coloring in the following setting: • We consider deterministic, synchronous algorithms. • Message size and local computations are unbounded. • We assume that the network is a directed ring with n nodes. • Nodes have unique labels (identifiers) from 1 to n. Remarks: • A generalization of the lower bound to randomized algorithms is pos-sible. • Except for restricting to deterministic algorithms, all the conditions above make a lower bound stronger: Any lower bound for synchronous algorithms certainly also holds for asynchronous ones. A lower bound that is true if message size and local computations are not restricted is clearly also valid if we require a bound on the maximal message size or the amount of local computations. Similarly also assuming that the ring is directed and that node labels are from 1 to n (instead of choosing IDs from a more general domain) strengthen the lower bound. • Instead of directly proving that 3-coloring a ring needs Ω(log ∗ n) rounds, we will prove a slightly more general statement. We will con-sider deterministic algorithms with time complexity r (for arbitrary r) and derive a lower bound on the number of colors that are needed if we want to properly color an n-node ring with an r-round algorithm. A 3-coloring lower bound can then be derived by taking the smallest r for which an r-round algorithm needs 3 or fewer colors