We show that no algorithm exists for deciding whether a nite task for three or more processors is wait-free solvable in the asynchronous read-write shared-memory model. This impossibility result implies that there is no constructive (recursive) characterization of wait-free solvable tasks. It also applies to other shared-memory models of distributed computing, such as the comparison-based model.
Gafni and Koutsoupias REF have shown, for the first time, that the wait-free solvability for three or more processes is undecidable in the eponymous asynchronous shared-memory model.
Three-Processor Tasks Are Undecidable
SIAM J. Comput
Computer Science