TY - GEN
T1 - Brief Announcement
T2 - 36th International Symposium on Distributed Computing, DISC 2022
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 - 2022/10/1
Y1 - 2022/10/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.
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.
KW - Broadcast Congested Clique
KW - CONGEST
KW - LOCAL
KW - hybrid model
KW - synchronous networks
UR - http://www.scopus.com/inward/record.url?scp=85140929262&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2022.43
DO - 10.4230/LIPIcs.DISC.2022.43
M3 - Conference contribution
AN - SCOPUS:85140929262
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Distributed Computing, DISC 2022
A2 - Scheideler, Christian
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 25 October 2022 through 27 October 2022
ER -