DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2024.19

A General Class of Reductions and Extension-Based Proofs

Authors: Yusong Shi and Weidong Liu

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 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 have been shown to be limited in power: there is no extension-based proof of the impossibility of a wait-free protocol for (n,k)-set agreement among n > k ≥ 2 processes. Previous work used a restricted class of reductions to show that there are no extension-based proofs of the impossibility of wait-free protocols for some other distributed computing problems. It is known that for a restricted class of reductions, if a task 𝒯 reduces to 𝒮 and 𝒯 has an augmented extension-based proof that it is impossible to solve in the NIS model, then so does 𝒮. We introduce multiple-instance extension-based proofs and show that, if 𝒯 reduces to multiple instances of 𝒮, instead of just one instance and 𝒯 has an augmented extension-based proof, then 𝒮 has a multiple-instance extension-based proof that it is impossible to solve in the NIIS model. We introduce a new version of extension-based proofs that can further our understanding of extension-based proofs and their limitations.

Cite as

Yusong Shi and Weidong Liu. A General Class of Reductions and Extension-Based Proofs. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.OPODIS.2024.19,
  author =	{Shi, Yusong and Liu, Weidong},
  title =	{{A General Class of Reductions and Extension-Based Proofs}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.19},
  URN =		{urn:nbn:de:0030-drops-225559},
  doi =		{10.4230/LIPIcs.OPODIS.2024.19},
  annote =	{Keywords: Reductions, Impossibility proofs, Extension-based proof}
}

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 Liu, Weidong

A General Class of Reductions and Extension-Based Proofs

Abstract

Cite as

Brief Announcement: Colorless Tasks and Extension-Based Proofs

Abstract

Cite as

Thanks for your feedback!

Could not send message