Electronic Notes in Theoretical Computer Science · 2005 · 48 citations · 14 references
ComputingComputer ScienceComputer SystemsComputer ArchitectureData StructuresFormal MethodsAutomata TheoryConcurrency ControlConcurrency VerificationConcurrent System VerificationModel CheckingVerificationAutomata SimulationBackward SimulationConcurrent Data Structure VerificationConcurrent Program VerificationForward SimulationLock-free AlgorithmsLock-free Data StructuresSimulation-based Verification
We describe an approach to verifying concurrent data structures based on simulation between two Input/Output Automata (IOAs), modelling the specification and the implementation. We explain how we used this approach in mechanically verifying a simple lock-free stack implementation using forward simulation, and briefly discuss our experience in verifying three other lock-free algorithms which all required the use of backward simulation.
14
Gerard J. Holzmann · IEEE Transactions on Software Engineering · 1997 · 3.8K citations
The existence of refinement mappings
Martı́n Abadi, Leslie Lamport · Theoretical Computer Science · 1991 · 734 citations