Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Sequential Verification of Serializability

Hagit Attiya, Ganesan Ramalingam, and Noam Rinetzky

Abstract

Serializability is a commonly used correctness condition in concurrent programming. When a concurrent module is serializable, certain other properties of the module can be verified by considering only its sequential executions. In many cases, concurrent modules guarantee serializability by using standard locking protocols, such as tree locking or two-phase locking. Unfortunately, according to the existing literature, verifying that a concurrent module adheres to these protocols requires considering concurrent interleavings. In this paper, we show that adherence to a large class of locking protocols (including tree locking and two-phase locking) can be verified by considering only sequential executions. The main consequence of our results is that in many cases, the (manual or automatic) verification of serializability can itself be done using sequential reasoning. We have implemented a shape analysis that uses sequential reasoning to verify that a concurrent heap-manipulating module adheres to the tree (hand-over-hand) locking protocol. Our analyzer also verifies other aspects of partial correctness such as memory safety, structural (shape) properties, and sortedness, as well as termination. We have used our analyzer to verify concurrent list and tree modules implementations that use an unbounded heap an allow for an unbounded number of threads. Our preliminary experimental results show that the sequential reduction greatly reduces the cost of the analysis. We note that, for the best of our knowledge, our analyzer is the first to be able to automatically analyze an implementation of concurrent tree which uses fine-grained locking.

Details

Publication typeInproceedings
Published inPrinciples of Programming Languages (POPL)
PublisherAssociation for Computing Machinery, Inc.
> Publications > Sequential Verification of Serializability