Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Proving Linearizability Via Non-atomic Refinement
| |
|
Proving Linearizability Via Non-atomic Refinement
John Derrick1 , Gerhard Schellhorn2 and Heike Wehrheim3 
| (1) |
Department of Computing, University of Sheffield, Sheffield, UK |
| (2) |
Universität Augsburg, Institut für Informatik, 86135 Augsburg, Germany |
| (3) |
Universität Paderborn, Institut für Informatik, 33098 Paderborn, Germany |
Abstract
Linearizability is a correctness criterion for concurrent objects. In this paper, we prove linearizability of a concurrent
lock-free stack implementation by showing the implementation to be a non-atomic refinement of an abstract stack. To this end, we develop a generalisation of non-atomic refinement allowing one to refine a single (Z)
operation into a CSP process. Besides this extension, the definition furthermore embodies a termination condition which permits
one to prove starvation freedom for the concurrent processes.
Keywords Object-Z - CSP - refinement - concurrent access - linearizability
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|