TY - GEN

T1 - Computing Power of Hybrid Models in Synchronous Networks

AU - Fraigniaud, Pierre

AU - Montealegre, Pedro

AU - Paredes, Pablo

AU - Rapaport, Ivan

AU - Ríos-Wilson, Martín

AU - Todinca, Ioan

N1 - Publisher Copyright:
© Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca.

PY - 2023/2/1

Y1 - 2023/2/1

N2 - 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 an 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 ∈ {0, 1}n together with an index i ∈ [n], Bob is given a binary vector y ∈ {0, 1}n together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean outA, and Bob must output a boolean outB, such that outA ∧ outB = xj ⊕ yi. We show that the communication complexity of XOR-Index is Ω(n) bits.

AB - 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 an 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 ∈ {0, 1}n together with an index i ∈ [n], Bob is given a binary vector y ∈ {0, 1}n together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean outA, and Bob must output a boolean outB, such that outA ∧ outB = xj ⊕ yi. We show that the communication complexity of XOR-Index is Ω(n) bits.

KW - Broadcast Congested Clique

KW - CONGEST

KW - LOCAL

KW - hybrid model

KW - synchronous networks

UR - http://www.scopus.com/inward/record.url?scp=85148653185&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.OPODIS.2022.20

DO - 10.4230/LIPIcs.OPODIS.2022.20

M3 - Conference contribution

AN - SCOPUS:85148653185

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 26th International Conference on Principles of Distributed Systems, OPODIS 2022

A2 - Hillel, Eshcar

A2 - Palmieri, Roberto

A2 - Riviere, Etienne

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 26th International Conference on Principles of Distributed Systems, OPODIS 2022

Y2 - 13 December 2022 through 15 December 2022

ER -