Download now Free registration required
Concurrent data structures are usually designed to satisfy correctness conditions such as sequential consistency and linearizability. In this paper, the authors consider the following fundamental question: what guarantees are provided by these conditions for client programs? They formally show that these conditions can be characterized in terms of observational refinement. Their study also provides a new understanding of sequential consistency and linearizability in terms of abstraction of dependency between computation steps of client programs.
- Format: PDF
- Size: 213.9 KB