Axioms for concurrent objects
Maurice P. Herlihy, J.M. Wing · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · 1987
Specification and verification techniques for abstract data types that have been successful for sequential programs can be extended in a natural way to provide the same benefits for concurrent programs. We propose an approach to specifying and verifying concurrent objects based on a novel correctness condition, which we call “linearizability.” Linearizability provides the illusion that each operation takes effect instantaneously at some point between its invocation and its response, implying that the meaning of a concurrent object's operations can still be given by pre- and post-conditions. In this paper, we will define and discuss linearizability, and then give examples of how to reason about concurrent objects and verify their implementations based on their (sequential) axiomatic specifications.
Cited by 173 works. doi:10.1145/41625.41627
Authors
References
- Communicating Sequential Processes
- Communicating sequential processes
- The temporal logic of programs
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
- Verifying properties of parallel programs
- An axiomatic proof technique for parallel programs I
- Proving Liveness Properties of Concurrent Programs
- The serializability of concurrent database updates
- Verification of Concurrent Programs. Part I. The Temporal Framework,
- Proof of Correctness of Data Representations