多方通信复杂度 | Codeboy's Blog

参与者、输入与信道

多方问题由函数

f:X_1\times\cdots\times X_k\to Z

和输入可见性规则共同给出。协议还要固定通信拓扑：blackboard 模型中每条消息对所有人可见；message-passing 模型按点对点边发送；coordinator 模型让玩家只与中心通信。相同输入分割在三种拓扑下可有不同总成本。

通信通常按所有实际发送 bit 的总和计，也可研究最大单玩家负载、轮数或每条链路拥塞。玩家数 $k$ 可能是常数，也可能随输入规模增长；把 $k$ 隐藏进 $O(\cdot)$ 会丢掉多方问题最重要的参数之一。

协议还要指定谁输出以及终止条件。Blackboard transcript 可让所有玩家读出公开叶标签；coordinator-only 输出则可能省去把答案广播回各节点的成本。

若玩家可中途掉线或输入异步到达，那会加入容错与调度语义，不属于标准多方通信定义。这里默认参与者集合和发言顺序按协议共同已知。

随机性需声明为全局 public coin、各玩家 private coins，还是部分共享。错误量词仍是先固定完整输入元组，再对协议随机性取概率。

Number-in-hand

在 number-in-hand（NIH）模型中，玩家 $i$ 只看到自己的块 $x_i$ 。这是两方私有输入的直接推广：没有通信时，每人都不知道其他 $k-1$ 份数据。

例如 $k$ 位玩家各持一个 bit $x_i$ ，要公开输出 parity $x_1\oplus\cdots\oplus x_k$ 。Blackboard 上让前 $k-1$ 位依次写出自己的 bit，最后一位写出总 parity，共 $k$ bit；若只让最后一位本地输出，可省最后回传 bit。

输入只有一 bit 不让总通信变成常数独立于 $k$ 。每位玩家的 bit 都可能翻转答案，协议必须让其影响穿过通信拓扑。

Number-on-forehead

在 number-on-forehead（NOF）模型中，输入仍分成 $x_1,\ldots,x_k$ ，但玩家 $i$ 看见除 $x_i$ 外的所有块。名字描绘自己的输入写在额头上，只有本人看不见。玩家拥有大量重叠信息，能力通常强于 NIH。

对三 bit parity，玩家 1 看到 $(x_2,x_3)$ ，可写 $x_2\oplus x_3$ ；玩家 2 看到 $x_1$ ，再写 $x_1$ 。所有人由两 bit blackboard transcript 得到总 parity。相比 NIH 的三 bit 协议，可见性重叠省掉一条消息。

这只是执行图像，不证明每个 NOF 问题都严格更容易。两种模型甚至没有逐问题简单包含关系，除非明确输入如何重新编码；下界必须针对正确的视野集合证明。

多方 Set Disjointness

在 NIH 版本中，每位玩家持有 $S_i\subseteq[n]$ ，常见目标判断

\bigcap_{i=1}^kS_i=\varnothing.

朴素 blackboard 协议让每位玩家写出 $n$ -bit 特征向量，再本地求逐位 AND，总通信 $kn$ bit。稀疏集合可发送元素列表，但成本变成 $O(\sum_i|S_i|\log n)$ ，并非无条件更小。

另一些文献把“集合不交”定义为任意两个集合都不相交，或让宇宙元素按玩家分块；这些任务的 yes/no 结构不同。引用多方 Disjointness 下界前，必须写清是共同交集为空还是 pairwise disjoint。

与两方归约

把 $k$ 位玩家分成两组，并让每组内部免费共享输入，可把多方协议压成两方协议，从而继承某些下界。但分组会改变各方可见信息和每轮哪些消息跨 cut；只有跨组 bit 才成为两方通信。

反方向把两方输入复制给许多玩家，可能产生额外共享信息，不能默认保持困难。有效归约需要逐玩家列出视野，并证明模拟不让任何一方看到原模型中不可见的数据。

失败边界

Blackboard 的一 bit 被所有人同时看见，点对点网络中向 $k-1$ 人广播可能要发送多份。以“写一次”计费的上界不能原样搬到 message-passing 总通信。

轮数也会改变能力。Simultaneous 模型每位玩家只向 referee 发一次消息，多方交互则允许根据早期消息协调；二者都叫 multiparty，却不能共用未注明轮数的复杂度。

最后，NOF 玩家看见“其他全部输入”不等于有一个中央 referee 看见全部输入。每个玩家仍缺一块，不同缺口如何交叠正是模型结构。

参考资料

László Babai, Noam Nisan, and Mario Szegedy, “Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs,” Journal of Computer and System Sciences 45(2), 1992, pp. 204–232.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 6.
David P. Woodruff and Qin Zhang, “When Distributed Computation Is Communication Expensive,” Distributed Computing 30, 2017, pp. 309–323.

参与者、输入与信道 ​

Number-in-hand ​

Number-on-forehead ​

多方 Set Disjointness ​