Formal Aspects of Computing · 2012 · 81 citations · 25 references
ComputingComputer ScienceComputer SystemsComputer ArchitectureFormal MethodsProgramming LanguagesAssertion-based VerificationConcurrent System VerificationMemory ModelingModel CheckingTransaction Processing SystemsVerificationTransactional MemoryTransactional Memory SemanticsTransactional Memory Verification
Abstract Over the last decade, great progress has been made in developing practical transactional memory (TM) implementations, but relatively little attention has been paid to precisely specifying what it means for them to be correct, or formally proving that they are. In this paper, we present TMS1 (Transactional Memory Specification 1), a precise specification of correct behaviour of a TM runtime library. TMS1 targets TM runtimes used to implement transactional features in an unmanaged programming language such as C or C++. In such contexts, even transactions that ultimately abort must observe consistent states of memory; otherwise, unrecoverable errors such as divide-by-zero may occur before a transaction aborts, even in a correct program in which the error would not be possible if transactions were executed atomically. We specify TMS1 precisely using an I/O automaton (IOA). This approach enables us to also model TM implementations using IOAs and to construct fully formal and machine-checked correctness proofs for them using well established proof techniques and tools. We outline key requirements for a TM system. To avoid precluding any implementation that satisfies these requirements, we specify TMS1 to be as general as we can, consistent with these requirements. The cost of such generality is that the condition does not map closely to intuition about common TM implementation techniques, and thus it is difficult to prove that such implementations satisfy the condition. To address this concern, we present TMS2, a more restrictive condition that more closely reflects intuition about common TM implementation techniques. We present a simulation proof that TMS2 implements TMS1, thus showing that to prove that an implementation satisfies TMS1, it suffices to prove that it satisfies TMS2. We have formalised and verified this proof using the PVS specification and verification system.
25
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
An Introduction to Input/Output Automata
Nancy Lynch, Mark R. Tuttle · Formal Aspects of Computing · 2026 · 1K citations · Full text
An axiomatic proof technique for parallel programs I
Susan Owicki, David Gries · Acta Informatica · 1976 · 1K citations
Hierarchical correctness proofs for distributed algorithms
Nancy Lynch, Mark R. Tuttle · 1987 · 767 citations · Full text
Bratin Saha, Ali-Reza Adl-Tabatabai, Richard L. Hudson et al. · 2006 · 493 citations