Modellkontroll programvara transaktionsminnen (STM) är svårt på grund av det obundna antalet, längd, och fördröjning av samtidiga transaktioner och den obegränsade storleken på minnet. Vi visar att under vissa förhållanden kan verifieringsproblemet reduceras till ett ändligt tillståndsproblem, och vi illustrerar användningen av metoden genom att bevisa att flera STM:er är korrekta, inklusive tvåfaslåsning, DSTM, TL2 och optimistisk konvergenskontroll. De säkerhetsegenskaper vi anser inkluderar strikt serialiserbarhet och opacitet; levande egenskaper inkluderar obstruktion frihet, livelock frihet, och vänta frihet. Vårt huvudsakliga bidrag ligger i strukturen på de bevis, som till stor del är automatiserade och inte begränsade till de STM som nämns ovan. I ett första steg visar vi att varje STM som har vissa strukturella egenskaper antingen bryter mot ett krav på säkerhet eller livlighet på något program med två trådar och två delade variabler, eller uppfyller kravet på alla program. I det andra steget använder vi en modellkontroll för att bevisa kravet på STM som tillämpas på ett generellt program med två trådar och två variabler. I säkerhetsfallet konstruerar modellkontrollen ett simuleringsförhållande mellan två noggrant konstruerade finit-state övergångssystem, det ena som representerar den givna STM tillämpas på ett mest allmänt program, och det andra representerar en mest liberal säker STM tillämpas på samma program. I liveness-fallet analyserar modellkontrollen rättvisa villkor på det givna STM-övergångssystemet.
Guerraoui m.fl. REF visade sig vara ett viktigt minskningsteorem som anger att TM-verifieringsproblemet kan reduceras till det mest allmänna problemet med två trådar och två delade variabler, när en utvärderad TM uppfyller en uppsättning av vissa villkor.
Model checking transactional memories
{'venue': "PLDI '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}