Skip to main content

Liveness−preserving Atomicity Abstraction

Alexey Gotsman and Hongseok Yang

Abstract

Modern concurrent algorithms are usually encapsulated in libraries, and complex algorithms are often constructed using libraries of simpler ones. We present the first theorem that allows harnessing this structure to give compositional liveness proofs to concurrent algorithms and their clients. We show that, while proving a liveness property of a client using a concurrent library, we can soundly replace the library by another one related to the original library by a generalisation of a well-known notion of linearizability. We apply this result to show formally that lock-freedom, an often-used liveness property of non-blocking algorithms, is compositional for linearizable libraries, and provide an example illustrating our proof technique.

Address
Zurich‚ Switzerland
Book Title
Proceedings of the 38th International Colloquium on Automata‚ Languages and Programming
ISBN
978−3−642−22011−1
Month
July
Pages
453–465
Publisher
Springer−Verlag
Series
Lecture Notes in Computer Science
Volume
6461
Year
2011