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

Sheng, Yilun ; Ellen, Faith

Extension-Based Proofs for Synchronous Message Passing

pdf-format:
LIPIcs-DISC-2021-36.pdf (0.6 MB)

Abstract

There is no wait-free algorithm that solves k-set agreement among n ≥ k+1 processes in asynchronous systems where processes communicate using only registers. However, proofs of this result for k ≥ 2 are complicated and involve topological reasoning. To explain why such sophisticated arguments are necessary, Alistarh, Aspnes, Ellen, Gelashvili, and Zhu recently introduced extension-based proofs, which generalize valency arguments, and proved that there are no extension-based proofs of this result.

In the synchronous message passing model, k-set agreement is solvable, but there is a lower bound of t rounds for any k-set agreement algorithm among n > kt processes when at most k processes can crash each round. The proof of this result for k ≥ 2 is also a complicated topological argument. We define a notion of extension-based proofs for this model and we show there are no extension-based proofs that t rounds are necessary for any k-set agreement algorithm among n = kt+1 processes, for k ≥ 2 and t > 2, when at most k processes can crash each round. In particular, our result shows that no valency argument can prove this lower bound.

BibTeX - Entry

@InProceedings{sheng_et_al:LIPIcs.DISC.2021.36,
  author =	{Sheng, Yilun and Ellen, Faith},
  title =	{{Extension-Based Proofs for Synchronous Message Passing}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{36:1--36:17},
  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/14838},
  URN =		{urn:nbn:de:0030-drops-148380},
  doi =		{10.4230/LIPIcs.DISC.2021.36},
  annote =	{Keywords: Set agreement, lower bounds, valency arguments}
}

Keywords: Set agreement, lower bounds, valency arguments
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