2026-08-07T07:37:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22555 2025-10-02T11:06:09Z ddc:004 open_access

A General Class of Reductions and Extension-Based Proofs Shi, Yusong Liu, Weidong Reductions Impossibility proofs Extension-based proof 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yusong Shi and Weidong Liu 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.19 urn:nbn:de:0030-drops-225559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode