Wait-free solvability via combinatorial topology
Date
1996Author
Mavronicolas, MariosSource
Proceedings of the Annual ACM Symposium on Principles of Distributed ComputingProceedings of the 1996 15th Annual ACM Symposium on Principles of Distributed Computing
Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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.