The FLINT Project

Research

People

Publications

Software

Support

Links

Internal

A Compositional Theory of Linearizability

Last modified: Mon Jan 23 00:11:31 2023 GMT.

Authors

Arthur Oliveira Vale
Zhong Shao
Yixuan Chen

Abstract

Compositionality is at the core of programming languages research and has become an important goal toward scalable verification of large systems. Despite that, there is no compositional account of linearizability, the gold standard of correctness for concurrent objects.

In this paper, we develop a compositional semantics for linearizable concurrent objects. We start by showcasing a common issue, which is independent of linearizability, in the construction of compositional models of concurrent computation: interaction with the neutral element for composition can lead to emergent behaviors, a hindrance to compositionality. Category theory provides a solution for the issue in the form of the Karoubi envelope. Surprisingly, and this is the main discovery of our work, this abstract construction is deeply related to linearizability and leads to a novel formulation of it. Notably, this new formulation neither relies on atomicity nor directly upon happens-before ordering and is only possible because of compositionality, revealing that linearizability and compositionality are intrinsically related to each other.

We use this new, and compositional, understanding of linearizability to revisit much of the theory of linearizability, providing novel, simple, algebraic proofs of the locality property and of an analogue of the equivalence with observational refinement. We show our techniques can be used in practice by connecting our semantics with a simple program logic that is nonetheless sound concerning this generalized linearizability.

Published

In Proc. 50th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'23), Boston, MA, January 2023. Published as Proceedings of the ACM on Programming Languages (PACMPL), Volume 7, Number POPL, Article 38 (January 2023), 32 pages.
  • Conference Paper [PDF]
  • POPL23 Talk Slides [PDF]
  • Extended Technical Report [PDF]

  • Copyright © 1996-2023 The FLINT Group <flint at cs dot yale dot edu>
    Yale University Department of Computer Science
    Validate this page
    colophon