Search

We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k \geq 2 processes or approximate agreement on a cycle of length 4 among n > 2 processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power. [ABSTRACT FROM AUTHOR]

An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future decisions of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future decisions, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, providing evidence that there are no local impossibility proofs for these tasks. • Studies impossibility proofs for sub-consensus tasks in wait-free shared-memory. • Locally-solvable valency tasks capture the FLP strategy for proving impossibility results. • Presents locally-solvable valency tasks for set consensus, weak symmetry breaking and renaming. • This explains why there are no FLP-style proofs for the impossibility of solving these tasks. [ABSTRACT FROM AUTHOR]