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$ 轮内解决。