1 Search Results for "Sheng, Yilun"

Document

DOI: 10.4230/LIPIcs.DISC.2021.36

Extension-Based Proofs for Synchronous Message Passing

Authors: Yilun Sheng and Faith Ellen

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.

Cite as

Yilun Sheng and Faith Ellen. Extension-Based Proofs for Synchronous Message Passing. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.36},
  URN =		{urn:nbn:de:0030-drops-148380},
  doi =		{10.4230/LIPIcs.DISC.2021.36},
  annote =	{Keywords: Set agreement, lower bounds, valency arguments}
}

Refine by Author
1 Ellen, Faith
1 Sheng, Yilun

Refine by Classification
1 Theory of computation → Complexity theory and logic
1 Theory of computation → Distributed algorithms
1 Theory of computation → Distributed computing models
1 Theory of computation → Interactive proof systems

Refine by Keyword
1 Set agreement
1 lower bounds
1 valency arguments

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Sheng, Yilun"

Extension-Based Proofs for Synchronous Message Passing

Abstract

Cite as

Thanks for your feedback!

Could not send message