E. Gafni and E. Koutsoupias.
Three-processor tasks are undecidable.
SIAM Journal on Computing, 28(3):970--983, 1999.
Abstract
We show that no algorithm exists for deciding whether a finite 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.Bib
@Article{GK99,
author = {E. Gafni and E. Koutsoupias},
title = {Three-Processor Tasks Are Undecidable},
journal = {SIAM Journal on Computing},
year = {1999},
volume = {28},
number = {3},
pages = {970--983}
}
@string{PODC95 = {Proceedings of the Fourteenth Annual ACM Symposium
on Principles of Distributed Computing}}
@InProceedings{GK95,
author = {E. Gafni and E. Koutsoupias},
title = {Three-processor tasks are undecidable},
booktitle = PODC95,
year = 1995,
month = {20--23 } # aug,
pages = 271,
address = {Ottawa, Ontario, Canada},
note = {Final version in Siam J. on Comp.}
}