Vi visar att det inte finns någon algoritm för att avgöra om en nite-uppgift för tre eller fler processorer är väntefri lösning i den asynkrona läs-skriva delade minnesmodellen. Detta omöjlighetsresultat innebär att det inte finns någon konstruktiv (rekursiv) karakterisering av vänta-fria lösa uppgifter. Det gäller även för andra delade minnesmodeller för distribuerade datorer, t.ex. den jämförelsebaserade modellen.
Gafni och Koutsoupias REF har för första gången visat att den väntefria lösligheten för tre eller fler processer är obeslutbar i den eponyma asynkrona delade minnesmodellen.
Three-Processor Tasks Are Undecidable
{'venue': 'SIAM J. Comput', 'journal': None, 'mag_field_of_study': ['Computer Science']}