Vi presenterar en ny teknik för att verifiera kommuteringsförhållandena, som är logiska formler som kännetecknar när operationer pendlar. Eftersom vår teknik resonerar med abstrakt tillstånd av verifierade länkade data struktur implementationer, det kan verifiera pendling verksamhet som producerar semantiskt likvärdiga (men inte nödvändigtvis identiska) datastruktur anger i olika utförande order. Vi har använt denna teknik för att verifiera ljud och fullständig kommutivitet villkor för alla par av operationer på en samling länkade datastruktur implementationer, inklusive datastrukturer som exporterar ett set gränssnitt (ListSet och HashSet) samt datastrukturer som exporterar ett kartgränssnitt (AssociationList, HashTable, och ArrayList). Detta arbete omfattade specificering och kontroll av 765 kommuteringsvillkor. Många spekulativa parallella system måste upphäva effekterna av spekulativt utförda operationer. Omvända operationer, som upphäver dessa effekter, är ofta effektivare än alternativa metoder (såsom att spara och återställa datastrukturtillstånd). Vi presenterar en ny teknik för att verifiera sådan omvänd verksamhet. Vi har specificerat och verifierat, för alla våra länkade datastrukturimplementeringar, en omvänd operation för varje operation som ändrar datastrukturtillståndet. Tillsammans ger kommuteringsvillkoren och omvänt verksamhet en nyckelresurs som språkdesigners, utvecklare av programanalyssystem och implementatorer av programvarusystem kan utnyttja för att bygga språk, programanalyser och system med starka korrekthetsgarantier.
I REF presenteras en teknik för att verifiera kommuteringsförhållandena, som är logiska formler som kännetecknar när operationer på en länkad datastruktur pendlar.
Verification of semantic commutativity conditions and inverse operations on linked data structures
{'venue': "PLDI '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}