License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.43
URN: urn:nbn:de:0030-drops-172345
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17234/
Go to the corresponding LIPIcs Volume Portal

Fraigniaud, Pierre ; Montealegre, Pedro ; Paredes, Pablo ; Rapaport, Ivan ; Ríos-Wilson, Martín ; Todinca, Ioan

Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks

pdf-format:
LIPIcs-DISC-2022-43.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.43,
  author =	{Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
  title =	{{Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17234},
  URN =		{urn:nbn:de:0030-drops-172345},
  doi =		{10.4230/LIPIcs.DISC.2022.43},
  annote =	{Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}

Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique
Collection: 36th International Symposium on Distributed Computing (DISC 2022)
Issue Date: 2022
Date of publication: 17.10.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI