Can I read Line-up: a Complete and Automatic Linearizability Checker on EtoBox?

Line-up: a Complete and Automatic Linearizability Checker by Sebastian Burckhardt; Chris Dern; Madanlal Musuvathi; Roy Tan is a scholarly article available to read on EtoBox.

What is Line-up: a Complete and Automatic Linearizability Checker about?

Modular development of concurrent applications requires threadsafe components that behave correctly when called concurrently by multiple client threads. This paper focuses on linearizability, a specific formalization of thread safety, where all operations of a concurrent component appear to take effect instantaneously at some point between their call and return. The key insight of this paper is that if a component is intended to be deterministic, then it is possible to build an automatic linearizability checker by systematically enumerating the sequential behaviors of the component and then checking if each its concurrent behavior is equivalent to some sequential behavior. We develop this insight into a tool called Line-Up, the first complete and automatic checker for deterministic linearizability. It is complete, because any reported violation proves that the implementation is not linearizable with respect to any sequential deterministic specification. It is automatic, requiring no manual abstraction, no manual specification of semantics or commit points, no manually written test suites, no access to source code. We evaluate Line-Up by analyzing 13 classes with a total of 90 metho

Author

Sebastian Burckhardt; Chris Dern; Madanlal Musuvathi; Roy Tan

Publisher

ACM

Published

2010

Language

EN