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.
My Menu
Saved Items

Proving Linearizability Via Non-atomic Refinement

John DerrickContact Information, Gerhard SchellhornContact Information and Heike WehrheimContact Information

(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


Contact Information John Derrick
Email: J.Derrick@dcs.shef.ac.uk

Contact Information Gerhard Schellhorn
Email: schellhorn@informatik.uni-augsburg.de

Contact Information Heike Wehrheim
Email: wehrheim@uni-paderborn.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.114 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)