Abstrakt. Vi undersöker den algoritmiska genomförbarheten av att kontrollera om samtidiga implementationer av delade minnesobjekt följer deras givna sekventiella specifikationer; sekventiell konsekvens, linjärisability, och konflikt serializability är kanoniska variationer av detta problem. Samtidigt verifiera sekventiell överensstämmelse av system med obundna konvergens är känt för att vara obeslutsamma, vi visar att konflikt serialisability, och linjärisability med fasta linjäriseringspunkter är EXPACE-fullständig, medan det allmänna linjärisability problemet är oavgjort. Våra (o)avgörande bevis, förutom att ge nya teoretiska resultat, avslöjar också nya program prospekteringsstrategier. Vi visar till exempel att varje överträdelse av konfliktens serialiseringsförmåga fångas upp av en konfliktcykel vars längd avgränsas oberoende av antalet samtidiga operationer. Detta tyder på en ofullständig detektionsalgoritm som bara kommer ihåg en liten delmängd av konfliktkanter, som kan göras komplett genom att öka antalet ihågkomna kanter till cykellängden bunden. På samma sätt, vår obeslutbarhet bevis för linjärisering tyder på en ofullständig detektionsalgoritm som begränsar antalet "barriärer" bisecting icke-överlappande operationer. Vårt decledability bevis på limned-barrier linearizability är intressant på egen hand, eftersom det minskar beaktandet av alla möjliga operation serialiseringar till numeriska begränsningar lösning. Litteraturen tycks bekräfta att de flesta överträdelser kan upptäckas genom att man betraktar mycket få konflikthärdar eller hinder.
REF visade att problemet blir oavgjort när antalet samtidiga transaktioner är obundna.
Verifying concurrent programs against sequential specifications
{'venue': 'ESOP', 'journal': None, 'mag_field_of_study': ['Computer Science']}