Model checking of linearizability of concurrent list implementations

Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. 2010. Model checking of linearizability of concurrent list implementations. CAV: Computer Aided Verification, LNCS, vol. 6174, 465–479.

Download
OA 2010_CAV_Cerny.pdf 3.63 MB [Submitted Version]

Conference Paper | Published | English
Author
Series Title
LNCS
Abstract
Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each vertex stores an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free implementation and proved that the corrected version is linearizable.
Publishing Year
Date Published
2010-07-01
Publisher
Springer
Volume
6174
Page
465 - 479
Conference
CAV: Computer Aided Verification
Conference Location
Edinburgh, UK
Conference Date
2010-07-15 – 2010-07-17
IST-REx-ID

Cite this

Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. Model checking of linearizability of concurrent list implementations. In: Vol 6174. Springer; 2010:465-479. doi:10.1007/978-3-642-14295-6_41
Cerny, P., Radhakrishna, A., Zufferey, D., Chaudhuri, S., & Alur, R. (2010). Model checking of linearizability of concurrent list implementations (Vol. 6174, pp. 465–479). Presented at the CAV: Computer Aided Verification, Edinburgh, UK: Springer. https://doi.org/10.1007/978-3-642-14295-6_41
Cerny, Pavol, Arjun Radhakrishna, Damien Zufferey, Swarat Chaudhuri, and Rajeev Alur. “Model Checking of Linearizability of Concurrent List Implementations,” 6174:465–79. Springer, 2010. https://doi.org/10.1007/978-3-642-14295-6_41.
P. Cerny, A. Radhakrishna, D. Zufferey, S. Chaudhuri, and R. Alur, “Model checking of linearizability of concurrent list implementations,” presented at the CAV: Computer Aided Verification, Edinburgh, UK, 2010, vol. 6174, pp. 465–479.
Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. 2010. Model checking of linearizability of concurrent list implementations. CAV: Computer Aided Verification, LNCS, vol. 6174, 465–479.
Cerny, Pavol, et al. Model Checking of Linearizability of Concurrent List Implementations. Vol. 6174, Springer, 2010, pp. 465–79, doi:10.1007/978-3-642-14295-6_41.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2020-05-19
MD5 Checksum
2eb211ce40b3c4988bce3a3592980704


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar