论文标题
同步网络中混合模型的计算能力
Computing Power of Hybrid Models in Synchronous Networks
论文作者
论文摘要
在过去的二十年中，出现了一系列的网络分布式计算模型，其中当地，拥塞和广播拥塞集团（BCC）发挥了重要作用。我们考虑组合这三个模型产生的混合模型。也就是说，我们分析了模型的计算能力，例如，允许执行恒定数量的交货次数，然后进行恒定的局部回合，然后是恒定的BCC回合数，可能会重复此数字恒定的次数。我们特别关注两轮模型，并建立了这些模型相对功能的完整图片。也就是说，对于每对此类模型，我们都会确定一个模型（严格地）是否比另一个更强，或者两个模型是否无与伦比。分离结果是通过通过原始角度接近通信复杂性来获得的，这可能具有独立的关注。这两个播放器并未有限来计算二进制函数的值，但是两个播放器的组合输出受此值的约束。特别是，我们介绍了XOR索引问题，其中为爱丽丝提供了二进制矢量$ x \ in \ {0,1 \}^n $以及index $ i \ in [n] $，bob被给予二进制矢量$ y \ y \ y \ y y \ in \ in \ in \ {0,1 \}^n $，in Index^n $ nive a in Index $ n nime a n nime a n offortiate a n offort a nouthiese a in a n a n in a n in a n a n y a n a n y]布尔$ \ textrm {out} _a $，而鲍勃必须输出布尔$ \ textrm {out} _b $，这样$ \ mbox {out} _a \ land \ land \ mbox {out} _b = x_jj \ x_j \ oplus y_i $。我们表明，XOR索引的通信复杂性为$ω（n）$位。
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $Ω(n)$ bits.
