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.2021.47
URN: urn:nbn:de:0030-drops-148492
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14849/
Go to the corresponding LIPIcs Volume Portal

Bastide, Paul ; Fraigniaud, Pierre

Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models

pdf-format:
LIPIcs-DISC-2021-47.pdf (0.4 MB)

Abstract

Given any task Π, Brandt’s speedup theorem (PODC 2019) provides a mechanical way to design another task Π' on the same input-set as Π such that, for any t ≥ 1, Π is solvable in t rounds in the LOCAL model if and only if Π' is solvable in t-1 rounds in the LOCAL model. We dissect the construction in Brandt’s speedup theorem for expressing it in the broader framework of all round-based models supporting full information protocols, which includes models as different as asynchronous wait-free shared-memory computing with iterated immediate snapshots, and synchronous failure-free network computing.

BibTeX - Entry

@InProceedings{bastide_et_al:LIPIcs.DISC.2021.47,
  author =	{Bastide, Paul and Fraigniaud, Pierre},
  title =	{{Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14849},
  URN =		{urn:nbn:de:0030-drops-148492},
  doi =		{10.4230/LIPIcs.DISC.2021.47},
  annote =	{Keywords: Local Checkability, Distributed Complexity and Computability}
}

Keywords: Local Checkability, Distributed Complexity and Computability
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

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