同时消息传递模型

三方协议形状 ​

Alice 持有 $x\in X$，Bob 持有 $y\in Y$，referee 没有私有输入。双方在看不到对方消息的情况下分别计算

$$M_A=A(x;R_A,R),M_B=B(y;R_B,R),$$

并各发送一次。Referee 用消息、自己的随机币及模型允许的公共随机串 $R$ 输出

$$G(M_A,M_B;R_R,R).$$

这称为 simultaneous message passing（SMP）。消息“同时”表示任一发送者都不能根据另一条消息调整内容；实现上先后到达不改变协议，只要发送规则在逻辑上独立。

通信成本可以取 $|M_A|+|M_B|$，也可报告较长一条消息 $max\{|M_A|,|M_B|\}$。两种 convention 相差至多因子 $2$，但精确常数和不对称协议仍需注明。Referee 的本地计算通常免费，最终输出不再回传给发送者。

随机币的三种可见性 ​

Private-coin SMP 让 $R_A,R_B,R_R$ 相互独立。给定输入后，两条消息条件独立，referee 只能从各自摘要的联合分布判断答案。

Public-coin SMP 让所有参与者看到同一条、与输入独立的 $R$。Alice 与 Bob 可以据此选同一个哈希函数或采样坐标，两条消息即使在给定 $(x,y)$ 后也会通过 $R$ 相关。公共串不计通信，却不能依赖当前输入。

还存在只由 Alice、Bob 共享而 referee 不知，或各方两两共享随机性的模型。它们不是 private/public 的同义写法；谁能看到哪个随机变量直接决定 referee 是否能解释消息相关性。

随机通信公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。的逐输入错误量词保持不变：对每个固定 $(x,y)$，概率只对允许的币取，错误至多 $\epsilon$。在某个输入分布上平均正确不够替代 worst-case SMP。

公共币 Equality 指纹 ​

对 $x,y\in \{0,1{\}}^n$ 的 Equality，公共串给出独立均匀向量 $r^{(1)},\dots ,r^{(k)}$。Alice 发送

$$a_j=⟨r^{(j)},x⟩mod2,$$

Bob 同时发送 $b_j=⟨r^{(j)},y⟩mod2$。Referee 接受当且仅当每个 $a_j=b_j$。

若 $x=y$，两条消息逐位相同，必然接受。若 $x\ne y$，每个内积指纹碰撞概率为 $1/2$，$k$ 次独立碰撞概率为 $2^{-k}$。两位发送者各发 $k$ bit，总通信 $2k$，不需要任何交互。

这条协议与单向 Equality 的指纹公式相似，但信息流不同：Bob 不负责计算输出，也看不到 Alice 消息；只有 referee 汇合两份摘要。把 referee 偷换成 Bob 会改变谁拥有 $y$、谁看见公共串以及通信计数。

Private coin 的真实差距 ​

没有共享随机性时，双方无法免费选择同一个随机线性函数。经典结果表明，private-coin classical SMP 对 Equality 达到常数错误需要 $\mathrm{\Theta }(\sqrt{n})$ bit，而 public-coin SMP 只需常数通信（对固定错误）。

上界可用双方各自抽取并发送适当大小的哈希样本，让 referee 通过碰撞统计判断相等；下界则证明过短且独立的消息分布无法保留足够碰撞结构。这里只记录模型分离，不把“发送一个私有哈希”误写成无需种子协调的公共指纹。

与交互和协调器模型的边界 ​

任意 SMP 协议都可由一般交互协议模拟：双方把消息发到其中一方或中央节点。但交互协议的第二条消息可以依赖第一条，SMP 不允许这种反馈，所以交互下界不能自动由 SMP 下界替代。

Coordinator 模型允许多位玩家与中心往返多轮；SMP referee 只被动收一次消息。若 referee 可以发挑战再收回复，模型已经接近 star-topology 交互通信。

消息长度之外还要声明消息是否量子、是否共享纠缠以及 referee 的测量。经典 private/public SMP 的结论不能直接套到量子通信公理库量子通信复杂度Quantum communication complexity允许双方交换量子寄存器并选择是否预共享纠缠，以 qubit 数、经典 bit 数和错误概率共同衡量协议。。

最后，消息统计相关不等于输入统计相关。即使输入独立，公共币也能让消息相关；即使输入高度相关，private-coin 消息在给定完整输入后仍由独立私有币生成。下界证明必须条件化正确的变量。

参考资料

• Andrew Chi-Chih Yao, “Some Complexity Questions Related to Distributive Computing,” STOC, 1979, pp. 209–213.
• László Babai and Peter G. Kimmel, “Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity,” Computational Complexity 7, 1997, pp. 266–276.
• Ilan Newman and Mario Szegedy, “Public vs. Private Coin Flips in One Round Communication Games,” STOC, 1996, pp. 561–570.