Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/9719
Title: | Verifying linearizability on TSO architectures |
Authors: | Derrick, J Smith, G Dongol, B |
Keywords: | Linearizability;Consistent memory model;TSO (Total Store Order);x86 multicore architecture |
Issue Date: | 2014 |
Publisher: | Springer Verlag |
Citation: | Lecture Notes in Computer Science, 8739, pp. 341 - 356, 2014 |
Abstract: | Linearizability is the standard correctness criterion for fine-grained, non-atomic concurrent algorithms, and a variety of methods for verifying linearizability have been developed. However, most approaches assume a sequentially consistent memory model, which is not always realised in practice. In this paper we define linearizability on a weak memory model: the TSO (Total Store Order) memory model, which is implemented in the x86 multicore architecture. We also show how a simulation-based proof method can be adapted to verify linearizability for algorithms running on TSO architectures. We demonstrate our approach on a typical concurrent algorithm, spinlock, and prove it linearizable using our simulation-based approach. Previous approaches to proving linearizabilty on TSO architectures have required a modification to the algorithm's natural abstract specification. Our proof method is the first, to our knowledge, for proving correctness without the need for such modification. |
URI: | http://link.springer.com/chapter/10.1007%2F978-3-319-10181-1_21 http://bura.brunel.ac.uk/handle/2438/9719 |
DOI: | http://dx.doi.org/10.1007/978-3-319-10181-1_21 |
ISSN: | 0302-9743 |
Appears in Collections: | Dept of Computer Science Research Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 240.42 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.