Round Elimination

参考：Juho Hirvonen and Jukka Suomela, Juho Hirvonen and Jukka Suomela
看起来很舒服的一本书。

我们考虑一类特殊的图：biregular trees。即一个$(d,\delta)$-biregular tree 是一个树，其中结点可以分成两个不相交的集合，其中一部分称为 active nodes（或 black node），另一部分称为 passive nodes（或 white node）。

每个 active node 都和且仅和$d$ 或 1 个 passive node 相连，而每个 passive node 都和且仅和$\delta$ 或 1 个 active node 相连。

例子如下，(a) 图是$(3,3)$-biregular tree，(b) 图是$(3,2)$-biregular tree：

接下来我们考虑这样 graph 表示的 network 上的分布式算法。
特别地，我们考虑一类问题 bipartite locally verifiable problem：形式化地，每个这样的问题都有三个参数$(\Sigma,\mathbf{A},\mathbf{P})$，其中

• $\Sigma$ 是一个 finite alphabet；
• $\mathbf{A},\mathbf{P}$ 都是 set of multisets of elements from $\Sigma$。其中，$\mathbf{A}$ 中的 multiset 大小都是$d$，$\mathbf{P}$ 中的 multiset 大小都是$\delta$。

要解决这样的一个 problem，我们需要让所有的 active node 给自己相邻的边进行标记，标记为$\Sigma$ 中的元素，使得：对于每个 active node $v$，如果它有$d$ 个相邻的边，假设它相邻的边被标记为$s_1,s_2,...,s_d$，那么$[s_1,s_2,...,s_d]\in \mathbf{A}$，并且对于每个 passive node $u$，如果它有$\delta$ 个相邻的边，假设它相邻的边被标记为$t_1,t_2,...,t_\delta$，那么$[t_1,t_2,...,t_\delta]\in \mathbf{P}$。

换句话说，$\mathbf{A},\mathbf{P}$ 分别表示了 active node 和 passive node 的相邻边合法标记的真值表。

---

我们看三个例子：譬如对于$(3,3)$-biregular tree，我们要用 5 种颜色对边进行染色，使得每个 node 相邻的边的颜色都不一样。那么$\Sigma=\{1,2,3,4,5\}$ 表示五种颜色，

$$\mathbf{A}=\mathbf{P}=\{[x,y,z]: x,y,z\in \Sigma \text{且} x,y,z \text{两两不同}\},$$

其中我们用$[x,y,z]$ 表示一个 multiset。

再看另一个例子：maximal matching。这个问题比较 tricky，我们需要$\Sigma=\{M,U,P\}$，其中

• $M$ 表示一个边在 matching 中；
• $U$ 表示一个边不在 matching 中，且该边的 active node 有相邻边在 matching 中；
• $P$ 表示一个边不在 matching 中，且该边的 active node 没有相邻边在 matching 中。

那么 active node 的约束就是

$$\mathbf{A}=\{[M,U,U],[P,P,P]\},$$

意思是：每个 active node 要么有一条边在 matching 中，要么三条边都不在 matching 中。而 passive node 的约束是

$$\mathbf{P}=\{[M,U,U],[M,P,U],[M,P,P],[U,U,U]\}.$$

这里就比较 tricky 了。对于一个 passive node，它有几种情况：

• 有一条边在 matching 中。此时另外两条边的另一个端点（active node）可以有一条相邻的边在 matching 中，也可以没有；所以有三种情况$[M,U,U],[M,U,P],[M,P,P]$。
• 没有边在 matching 中。此时这三条边的另一个端点（active node）都必须有一条相邻的边在 matching 中；所以只能是$[U,U,U]$。

最后一个例子是 3-weak labeling，对于一个$(3,2)$-biregular tree，我们要用 3 种颜色对边进行染色，使得每个 active node 相邻的边的颜色只有 2 种，每个 passive node 相邻的边的颜色只有 1 种。即

$$\Sigma=\{1,2,3\},\quad \mathbf{A}=\{[1,1,2],[1,1,3],[2,2,1],[2,2,3],[3,3,1],[3,3,2]\},\quad \mathbf{P}=\{[1,1],[2,2],[3,3]\}.$$

---

接下来我们考虑 round elimination 要干什么。
它是用于证明 lower bound 的工具，基本想法是：对于一个 bipartite locally verifiable problem $\Pi_0=(\Sigma_0,\mathbf{A}_0,\mathbf{P}_0)$，如果我们可以构造出一个新的 bipartite locally verifiable problem $\Pi_1=(\Sigma_1,\mathbf{A}_1,\mathbf{P}_1)$，使得：如果$\Pi_0$ 可以在$t$ 轮内解决，那么$\Pi_1$ 可以在$t-1$ 轮内解决。

那么这样的话，如果有问题$\Pi_0,\Pi_1,...,\Pi_t$，那么$\Pi_t$ 应该是一个 trivial 的问题，它只需要 0 轮就可以解决，换句话说，解决$\Pi_t$ 不需要任何通讯。

如果我们发现$\Pi_t$ 不是一个 trivial 的问题，那么就说明$\Pi_0$ 至少需要$t+1$ 轮才能解决，这就证明了$\Pi_0$ 的 lower bound。

形式化地，令$\Pi_0=(\Sigma_0,\mathbf{A}_0,\mathbf{P}_0)$ 是$(d,\delta)$-biregular tree 上的一个 bipartite locally verifiable problem，我们如此构造$\Pi_1=(\Sigma_1,\mathbf{A}_1,\mathbf{P}_1)$：

• active node 和 passive node 交换角色。换句话说，$\Pi_1$ 是$(\delta,d)$-biregular tree 上的一个 bipartite locally verifiable problem；
• $\Sigma_1$ 是$\Sigma_0$ 的所有非空子集；
• active configurations $\mathbf{A}_1$ 为

  $$\mathbf{A}_1=\{[X_1,...,X_\delta]:X_1,...,X_\delta\in \Sigma_1\text{ s.t. }\forall x_i\in X_i,\ [x_1,...,x_\delta]\in \mathbf{P}_0\}.$$

• passive configurations $\mathbf{P}_1$ 为

  $$\mathbf{P}_1=\{[Y_1,...,Y_d]:Y_1,...,Y_d\in \Sigma_1\text{ s.t. }\exists y_i\in Y_i,\ [y_1,...,y_d]\in \mathbf{A}_0\}.$$

譬如回看之前的 3-weak labeling 问题，我们有

• $\Sigma_1=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$;
• $\mathbf{A}_1=\{[\{1\},\{1\}],[\{2\},\{2\}],[\{3\},\{3\}]\}$;
• $\mathbf{P}_1=\{[\{1\},\{1\},\{2\}],[\{1\},\{1\},\{3\}],[\{2\},\{2\},\{1\}],[\{2\},\{2\},\{3\}],[\{3\},\{3\},\{1\}],[\{3\},\{3\},\{2\}]\}$。
  注意，按照定义$\mathbf{P}_1$ 应该含有更多的情况，譬如$[\{1,2,3\},\{1,2,3\},\{1,2,3\}]$，因为根据定义只需要存在性。但是因为 active configurations 中只有单点集合，意味着合法的对边标记都是$\Sigma_1$ 中的那些单点集，因此在 passive configuration 时我们也只考虑了单点集的约束（其余情况必定不满足 active 约束）。

---

接下来我们进入最核心的部分：假设$\Pi_0$ 可以在$T$ 轮内解决，我们证明$\Pi_1$ 可以在$T-1$ 轮内解决。

对于每个$\Pi_1$-active node $u$，在$T-1$ 轮内，它都可以获取所有$\mathrm{ball}(u,T-1)$ 范围内的所有 node 的信息，其中$\mathrm{ball}(u,r)$ 表示以$u$ 为中心，范围在$r$ 内的子图。

基本想法是：对于$u$ 的每个邻居$v$，$v$ 是$\Pi_0$-active node。然后$u$ 需要去枚举所有可能的$v$ 的$\mathrm{Ball}(v,T)$。每枚举到一个情况，就可以运行$\Pi_0$ 的算法，然后得出一个$(u,v)$ 边的标记（$\Sigma_0$ 中的标记）。

因此把所有可能的标记放在一起，就得到了一个集合$S(u,v)\in\Sigma_1$，这个集合就是边$(u,v)$ 在$\Pi_1$ 中的标记。

先看个例子，譬如下图$(3,2)$-biregular tree 中，一个$\Pi_1$-active node $u$，它的$\mathrm{ball}(u,3)$ 区域由灰色画出。而它的两个邻居$v,w$ 的$\mathrm{ball}(v,4),\mathrm{ball}(w,4)$ 区域由蓝色 + 灰色和红色 + 灰色画出。

那么$u$ 需要枚举蓝色范围所有可能的子图结构，使得它成为一个$(3,2)$-biregular tree。注意，$u$ 至多只能知道灰色范围内的信息，因此它无从得知灰色外的图长什么样子！所以他需要枚举，枚举$\mathrm{ball}(v,T)$ 灰色外的图长什么样子。

然后$u$ 运行$\Pi_0$ 的算法，得到$(u,v)$ 边的标记。类似地得到$(u,w)$ 边的标记。

我们接下来说明，这样做的确得到了一个满足$\Pi_1$ 约束的解。

是这样子的，我们考虑$u$ 的邻居$v_1,...,v_\delta$ 以及上述模拟的输出$x_1\in S(u,v_1),...,x_\delta\in S(u,v_\delta)$。

注意，我们知道对于$\Pi_0$ 的算法，它应该可以处理所有可能的 graph 结构：即对于任意枚举到的情况，模拟算法得到的标记方式都应该满足$\Pi_0$ 中对$u$ 的约束（这是 local 的），即

$$[x_1,x_2,...,x_\delta]\in \mathbf{P}_0.$$

这部分需要仔细想一下，就是无论外侧的图长什么样子，模拟$\Pi_0$ 上算法的结果一定会导致$(u,v)$ 边的标记都符合$\Pi_0$ 中对$u$ 的约束。看看上图，以 maximal matching 为例，思考一下。

而考虑$\Pi_1$-passive node $v$，因为它的所有邻居都是$\Pi_0$-active node，然后每个邻居$u$ 都会去尝试枚举那些不在$\mathrm{ball}(u,T)$ 中部分的$\mathrm{ball}(v,T-1)$。

即使多个$u$ 之间枚举的结构之间不一定 compatible，即有可能不存在一个 underlying graph 同时满足所有$u$ 枚举的结构，但是总是存在一个枚举的情况使得这些结构是合法的。因此，是存在一个$x_1\in S(u_1,v),...,x_d\in S(u_d,v)$ 使得

$$[x_1,x_2,...,x_d]\in \mathbf{A}_0.$$

总之，要尝试理解：以$\Pi_1$-active node 去枚举的话，那么所有$\Pi_1$-active 的约束都会被满足，因为 active node 枚举到的都是合法的情况；但$\Pi_1$-passive 的约束不一定被满足，因为和 passive 相连的边是由 active node 决定的。但是总是会枚举到真实情况，从而满足约束，这也就是为什么这么构造$\Pi_1$。

---

接下来我们回看之前的 3-weak labeling 的问题，我们知道它无法在 1 轮内解决。
因为考虑$\Pi_1$，在没有通讯的情况下，所有 active node 只知道自己的信息（以及和自己相邻的边在自己这边的 port number），因此所有 active node 为了满足约束

$$\mathbf{A}_1=\{[\{1\},\{1\}],[\{2\},\{2\}],[\{3\},\{3\}]\},$$

都会把和自己相邻的 2 条边都设置成同一个 label $X\in\{\{1\},\{2\},\{3\}\}$。
这样做的结果就是违反了 passive 约束，因为$[X,X,X]\cancel\in \mathbf{P}_1$。

但是 3-weak labeling 实际上可以在 2 轮内解决。一个必要条件就是，两次 round elimination 后得到的$\Pi_2$ 必须是 0 轮可解的 trivial 问题。

我们等价地描述先前的$\Pi_1$ 问题，即

$$\Sigma_1=\{1,2,3\},\quad \mathbf{A}_1=\{[1,1],[2,2],[3,3]\},\quad \mathbf{P}_1=\{[1,1,2],[1,1,3],[2,2,1],[2,2,3],[3,3,1],[3,3,2]\}.$$

那么$\Sigma_2=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$，且

$$\begin{aligned} \mathbf{A}_2 &=\{[X,Y,Z]:X\subseteq \{1,2\},Y\subseteq \{1,3\},Z\subseteq \{2,3\}\}\\ &\cup \{[X,Y,Z]:X\subseteq \{1\},Y\subseteq \{2,3\},Z\subseteq \{1,2,3\}\}\\ &\cup \{[X,Y,Z]:X\subseteq \{2\},Y\subseteq \{1,3\},Z\subseteq \{1,2,3\}\}\\ &\cup \{[X,Y,Z]:X\subseteq \{3\},Y\subseteq \{1,2\},Z\subseteq \{1,2,3\}\}. \end{aligned}$$

而且

$$\mathbf{P}_2=\{[X,Y]:X,Y\in\Sigma_2,X\cap Y\neq\emptyset\}.$$

实际上$\Pi_2$ 是可以 0 轮解决的，因为所有 active node 都可以把和自己相邻的 3 条边分别标记为$\{1,2\},\{1,3\},\{2,3\}$，这样就满足 active 和 passive 的约束了。注意，$\Pi_2$ 中的 active node 是$\Pi_1$ 中的 passive node，因此它有 3 条边。