Reductions and Extension-Based Proofs
Kayman Brusse, Faith Ellen · 2021
In the theory of distributed computing, the notion of a reduction is a common tool for proving impossibility results. If task T reduces to task S, and T is impossible to solve, then so is S. Extension-based proofs demonstrate the impossibility of solving a task in a wait-free manner by constructing an infinite execution. It is known that extension-based proofs are limited in power: there is no extension-based proof of the impossibility of a wait-free protocol in the NIS model for k-set agreement among n > k ≥ 2 processes.