International Symposium on Distributed Computing

Distributed Computing pp 371-387

Modular Verification of Concurrency-Aware Linearizability

Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 9363)


Linearizability is the de facto correctness condition for concurrent objects. Informally, linearizable objects provide the illusion that each operation takes effect instantaneously at a unique point in time between its invocation and response. Hence, by design, linearizability cannot describe behaviors of concurrency-aware concurrent objects (CA-objects), objects in which several overlapping operations “seem to take effect simultaneously”. In this paper, we introduce concurrency-aware linearizability (CAL), a generalized notion of linearizability which allows to formally describe the behavior of CA-objects. Based on CAL, we develop a thread- and procedure-modular verification technique for reasoning about CA-objects and their clients. Using our new technique, we present the first proof of linearizability of the elimination stack of Hendler et al. [10] in which the stack’s elimination subcomponent, which is a general-purpose CA-object, is specified and verified independently of its particular usage by the stack.

Copyright information

© Springer-Verlag Berlin Heidelberg 2015

Authors and Affiliations

  1. 1.Tel Aviv UniversityTel AvivIsrael
  2. 2.MPI-SWSKaiserslauternGermany

Personalised recommendations