参考：https://disco.ethz.ch/courses/podc/#peleg

# Chapter 1: Tree Coloring Problem

考虑这样一个问题：给定一棵树，要求对树进行染色，让相邻的结点（父子之间）颜色不同。

很显然，2 种颜色就已经足够给一棵树染色，只要不同层之间交替使用颜色即可，但是这不可避免地要遍历树。

我们考虑 同步分布式计算 (synchronous) 的模型，即一轮一轮地进行通讯和计算：每一轮每个节点都可以给他的 neighbours 发消息（也可以从 neighbours 接收消息），然后进行本地计算。

即使我们给每个 vertex 对应分布式系统中的一个 node，那么它的颜色也需要等待从根节点一次次传递下来确定。换句话说，这个过程需要$O(h)$ 的通讯轮数 (round complexity)，其中$h$ 是树的高度。

注意，这里我们假设了分布式系统 node 之间的连接关系至少是和树的结构是一样的，即每个 node 都可以给自己的父子结点收发信息。

这样的算法效率不高，因为那些叶子结点在前几轮通讯时都在发呆，只有等父亲结点在某一轮确定颜色后，才会在下一轮确定自己的颜色。

我们再给出一个 distributed 算法。

• 每个结点都对应一个分布式系统中的一个节点；
• 初始时，每个结点的颜色就是它的编号，这样的话一共使用了$n$ 种颜色；
• 重复如下过程，直到所有结点的颜色都在$\{0,1,...,5\}$ 中：
  1. 每个结点都把它的颜色编号$c_v$ 发给所有的孩子，并从父亲结点那里接收颜色编号$c_p$；
  2. 把$c_v,c_p$ 表示为二进制形式，令$i$ 为 rightmost bit where $c_v$ and $c_p$ differ。每个结点把自己的颜色更新为$2i+(c_v)_i$。

举个例子，譬如$c_p=656=(10,1001,0000)_2$，$c_v=400=(01,1001,0000)_2$，那么$i=8$，更新后$c_v=2\cdot 8+1=17$。

这个算法第一眼看上去极度诡异，它是从一个 trivial 的正确染色方法开始（即所有 vertex 颜色都不一样），然后一步步更新颜色，直到最后用少于 6 种颜色。它的 round complexity 是惊人的$O(\log^*(n))$，其中$\log^*(n)$ 函数是如下定义的增长极度缓慢的函数：

$$\log^*(n)=\begin{cases} 1, & n\leq 2;\\ 1+\log^*(\log n), & n>2. \end{cases}$$

换句话说，$\log^*(n)=$ 需要用多少个$\log$ 函数才能把$n$ 缩小到不超过 2。可以注意到，$\log^*(10^80)=5$，即$\log\log\log\log\log 10^{80}\leq 2$，这已经是宇宙中所有原子数量。

下面我们证明这个算法的正确性和 round complexity。

首先是正确性，我们证明每次更新后，每个结点和它父亲结点的颜色仍不一样。
如果结点$v$ 和它父亲结点$p$ 的颜色在第$i$ 位不同，而$p$ 又和它的父亲颜色在第$j$ 位不同，那么有 2 种情况：

• $i\neq j$，那么更新后的颜色$c_v=2i+(c_v)_i$ 一定不等于$c_p=2j+(c_p)_i$。
• $i=j$，那么我们知道$(c_v)_i\neq (c_p)_i$，因此更新后的颜色仍然不同。

接下来是 round complexity，很显然每次都会使得最大颜色值缩减一个$\log$ 级别，因此最多$O(\log^*(n))$ 轮后，所有颜色都在$\{0,1,...,5\}$ 中。

为什么颜色最大是 5？可以验证，如果$c_v=5,c_p=1$，那么更新后$c_v$ 仍然是 5。但如果$c_v=6$ 或 7，那么它仍然是可以更新缩小的。

我们仍然忽视了很多东西，譬如最后一行：怎么才能让所有 node 都知道，所有 node 的颜色都在$\{0,1,...,5\}$ 中呢？这个问题的回答出奇地复杂。我们可能会固定一个轮数让每个 node 提前都知道，这样的话实际上每个 node 都需要知道$n$ 来计算$\log^*(n)$（而不是把轮数在某个结点上计算好后，通讯发给大家），这并不是很有效的办法。

接下来，我们优化到只用 3 个颜色染色。在前述算法的基础上，我们可以增加 6 轮通讯：

• for $x=5,4,3$，执行下面过程
  1. 用一轮通讯，使得所有结点的颜色都更新为它父结点的颜色。特别地，root 从$\{0,1,2\}$ 中找一个新的、不同于之前 root 颜色的颜色。
  2. 如果更新后的颜色等于$x$，用一轮通讯得知它父亲结点的颜色，并从$\{0,1,2\}$ 中找到一个合法颜色（即不同于它父子结点颜色的颜色，它孩子结点的颜色就是它原先的颜色）更新自己的颜色。

自己试一下就可以知道，为什么会有 1. 中那个 “push down” 的操作：保证了每个结点的所有孩子结点颜色一样。这样的话对于一个结点，相当于只有 2 种颜色：父亲的颜色和孩子的颜色。因此总是可以从 3 种颜色中找到一个不同于父子颜色的新的合法颜色。

但是如果想优化到用 2 个 color 染色的话，round complexity 会比$O(\log^*(n))$ 要指数级别大。

接下来我们把算法推广到$\Delta$-regular 图上，即每个结点都有$\Delta$ 个邻居。

那么我们把每个结点的初始颜色扩展到$\Delta\cdot \log n$ bits $(c_1,c_2,...,c_\Delta)$，即$\Delta$ 个原先 tree 上颜色的 tuple。那么每次更新时，我们可以把每个$c_i$ 和它的第$i$ 个邻居进行比较，然后和 tree 情况一样来构造新的颜色。

这样的话，只需要$O(\log^*(n))$ 轮，每个结点的颜色就只剩下$3\cdot \Delta$ bits 了，因为$\{0,1,2,3,4,5\}$ 只需要 3 bits 表示。最后，我们再采用类似的办法，可以优化到用$\Delta+1$ 个颜色完成染色，而不是$2^{3\Delta}$ 种颜色。

后续会给出一个对于一般图情况，在$O(\log n)$ 轮内用$\Delta+1$ 种颜色染色的算法。