Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable. SIAM Journal on Computing, 28(3):970--983, 1999.
Download: pdf ps


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.


  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}}

  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.}