Wait-free solvability via combinatorial topology
SourceProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Proceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing
Google Scholar check
MetadataShow full item record
This paper addresses the question of whether Algebraic Topology is really necessary for determining the characterization of solvable tasks for the case of general t. A Combinatorial Topology framework, totally bypassing Algebraic Topology is introduced within which, a simple, combinatorial characterization of wait-free tasks is presented. It is shown that this combinatorial condition implies necessary connectivity conditions for input complexes of wait-free tasks, reminiscent to corresponding conditions. Applications of the combinatorial characterization results are presented.