DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2024.54

Brief Announcement: Colorless Tasks and Extension-Based Proofs

Authors: Yusong Shi and Weidong Liu

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

The concept of extension-based proofs models the idea of a valency argument, which is widely used in distributed computing. Extension-based proofs are limited in power: it has been shown that there is no extension-based proof of the impossibility of a wait-free protocol for (n,k)-set agreement among n > k ≥ 2 processes. There are only a few tasks that have been proven to have no extension-based proof of the impossibility, since the techniques in these works are closely related to the specific task. We give a necessary and sufficient condition for colorless tasks to have no extension-based proofs of the impossibility of wait-free protocols in the NIIS model. We introduce a general adversarial strategy decoupled from any concrete task specification. In this strategy, some properties of the chromatic subdivision that is widely used in distributed computing are proved.

Cite as

Yusong Shi and Weidong Liu. Brief Announcement: Colorless Tasks and Extension-Based Proofs. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 54:1-54:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.DISC.2024.54,
  author =	{Shi, Yusong and Liu, Weidong},
  title =	{{Brief Announcement: Colorless Tasks and Extension-Based Proofs}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{54:1--54:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.54},
  URN =		{urn:nbn:de:0030-drops-212821},
  doi =		{10.4230/LIPIcs.DISC.2024.54},
  annote =	{Keywords: Colorless tasks, Impossibility proofs, Extension-based proof}
}

Search Results

Documents authored by Shi, Yusong

Brief Announcement: Colorless Tasks and Extension-Based Proofs

Abstract

Cite as

Thanks for your feedback!

Could not send message