License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.23
URN: urn:nbn:de:0030-drops-98124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9812/
Feldman, Yotam M. Y. ;
Enea, Constantin ;
Morrison, Adam ;
Rinetzky, Noam ;
Shoham, Sharon
Order out of Chaos: Proving Linearizability Using Local Views
Abstract
Proving the linearizability of highly concurrent data structures, such as those using optimistic concurrency control, is a challenging task. The main difficulty is in reasoning about the view of the memory obtained by the threads, because as they execute, threads observe different fragments of memory from different points in time. Until today, every linearizability proof has tackled this challenge from scratch.
We present a unifying proof argument for the correctness of unsynchronized traversals, and apply it to prove the linearizability of several highly concurrent search data structures, including an optimistic self-balancing binary search tree, the Lazy List and a lock-free skip list. Our framework harnesses sequential reasoning about the view of a thread, considering the thread as if it traverses the data structure without interference from other operations. Our key contribution is showing that properties of reachability along search paths can be deduced for concurrent traversals from such interference-free traversals, when certain intuitive conditions are met. Basing the correctness of traversals on such local view arguments greatly simplifies linearizability proofs. At the heart of our result lies a notion of order on the memory, corresponding to the order in which locations in memory are read by the threads, which guarantees a certain notion of consistency between the view of the thread and the actual memory.
To apply our framework, the user proves that the data structure satisfies two conditions: (1) acyclicity of the order on memory, even when it is considered across intermediate memory states, and (2) preservation of search paths to locations modified by interfering writes. Establishing the conditions, as well as the full linearizability proof utilizing our proof argument, reduces to simple concurrent reasoning. The result is a clear and comprehensible correctness proof, and elucidates common patterns underlying several existing data structures.
BibTeX - Entry
@InProceedings{feldman_et_al:LIPIcs:2018:9812,
author = {Yotam M. Y. Feldman and Constantin Enea and Adam Morrison and Noam Rinetzky and Sharon Shoham},
title = {{Order out of Chaos: Proving Linearizability Using Local Views}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {23:1--23:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9812},
URN = {urn:nbn:de:0030-drops-98124},
doi = {10.4230/LIPIcs.DISC.2018.23},
annote = {Keywords: concurrency and synchronization, concurrent data structures, lineariazability, optimistic concurrency control, verification and formal methods}
}
|
Keywords: |
|
concurrency and synchronization, concurrent data structures, lineariazability, optimistic concurrency control, verification and formal methods |
|
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.10.2018 |
