2026-07-22T11:39:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17234 2024-03-06T10:59:17Z ddc:004 open_access

Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks Fraigniaud, Pierre Montealegre, Pedro Paredes, Pablo Rapaport, Ivan Ríos-Wilson, Martín Todinca, Ioan hybrid model synchronous networks LOCAL CONGEST Broadcast Congested Clique 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Fraigniaud and Pedro Montealegre and Pablo Paredes and Ivan Rapaport and Martín Ríos-Wilson and Ioan Todinca 2022 Is Part Of LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2022.43 urn:nbn:de:0030-drops-172345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.43 eng https://creativecommons.org/licenses/by/4.0/legalcode