University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Making Linearizability Compositional for Partially Ordered Executions

Doherty, Simon, Dongol, Brijesh, Wehrheim, Heike and Derrick, John (2018) Making Linearizability Compositional for Partially Ordered Executions In: International Conference on Integrated Formal Methods - IFM 2018, 05-07 Sep 2018, Maynooth University, Ireland.

Making Linearizability Compositional for Partially Ordered Executions.pdf - Accepted version Manuscript

Download (392kB) | Preview


In the interleaving model of concurrency, where events are totally ordered, linearizability is compositional: the composition of two linearizable objects is guaranteed to be linearizable. However, linearizability is not compositional when events are only partially ordered, as in the weak-memory models that describe multicore memory systems. In this paper, we present a generalisation of linearizability for concurrent objects implemented in weak-memory models. We abstract from the details of specific memory models by defining our condition using Lamport's execution structures. We apply our condition to the C11 memory model, providing a correctness condition for C11 objects. We develop a proof method for verifying objects implemented in C11 and related models. Our method is an adaptation of simulation-based methods, but in contrast to other such methods, it does not require that the implementation totally orders its events. We apply our proof technique and show correctness of the Treiber stack that blocks on empty, annotated with C11 release-acquire synchronisation.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Doherty, Simon
Wehrheim, Heike
Derrick, John
Date : 9 August 2018
DOI : 10.1007/978-3-319-98938-9_7
Copyright Disclaimer : © Springer Nature Switzerland AG 2018
Depositing User : Clive Harris
Date Deposited : 17 Sep 2018 09:09
Last Modified : 31 Jan 2019 08:56

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800