Efficient Linearizability Monitoring

Parosh Aziz Abdulla, Samuel Grahn, Bengt Jonsson, S. Krishna, Om Swostik Mishra · 2025

Read Efficient Linearizability Monitoring by Parosh Aziz Abdulla, Samuel Grahn, Bengt Jonsson, S. Krishna, Om Swostik Mishra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-17795.txt.

Introduction

Parosh Aziz Abdulla and 4 co-authors speed up checks that a shared data store acted in a fair order. Their 2025 paper deals with stacks, queues, sets, and multisets used by many tasks at once. Given a log of calls, the check asks if some fair serial order fits it.

Their methods run in far less time than past cubic ones. Past work also had proof flaws, which the authors show with counter cases. A tool built from the new stack and queue methods beat the top past tool in tests. Full proofs back each new method, step by step.

Catalog record

CREATORParosh Aziz Abdulla, Samuel Grahn, Bengt Jonsson, S. Krishna, Om Swostik Mishra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-17795

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Linearizability Monitoring Parosh Aziz Abdulla, Samuel Grahn, Bengt Jonsson, S. Krishna, Om Swostik Mishra Abstract . This paper revisits the fundamental problem of monitoring the linearizability of concurrent stacks, queues, sets, and multisets. Given a history of a library implementing one of these abstract data types, the monitoring problem is to answer whether the given history is linearizable. For stacks, queues, and (multi)sets, we present monitoring algorithms with complexities 𝒪 ⁡ ( n 2 ) {\mathcal{O}}(n^{2}) , 𝒪 ⁡ ( n ​ l ​ o ​ g ​ n ) {\mathcal{O}}(n\;log\,n) , and 𝒪 ⁡ ( n ) {\mathcal{O}}{(n)} , respectively, where n n is the number of operations in the input history. For stacks and queues, our results hold under the standard assumption of data-independence , i.e., the behavior of the library is not sensitive to the actual values stored in the data structure. Past works to solve the same problems have cubic time complexity and (more seriously) have correctness issues: they either (i) lack correctness proofs or (ii) the suggested correctness proofs are erroneous (we present counter-examples), or (iii) have incorrect algorithms. Our improved complexity results rely on substantially different algorithms for which we provide detailed proofs of correctness. We have implemented our stack and queue algorithms in LiMo \sc{LiMo} (Linearizability Monitor). We evaluate LiMo \sc{LiMo} and compare it with the state-of-the-art tool Violin \sc{Violin} – whose correctness proofs we have found errors in – which checks for linearizability violations. Our experimental evaluation confirms that LiMo \sc{LiMo} outperforms Violin \sc{Violin} regarding both efficiency and scalability. 1. Introduction In concurrent programs, inter-thread communication is often performed using libraries that implement shared data structures, specified as abstract data types {\mathsf{ADT}} s, such as stacks, queues, sets, counters, snapshots, etc. Such a library, together with its clients, can be considered as a collection of threads running concurrently and communicating through the shared data structure. Each thread executes a sequence of operations on the library, issuing calls (invocations) followed by receiving the associated responses. Traditionally, we refer to an execution of the system as a history . The design of concurrent libraries implementing {\mathsf{ADT}} s is tricky. On the one hand, thread synchronization should be minimal to decrease communication and increase throughput. On the other hand, we need sufficient synchronization to guarantee the correctness of the library. Given the ubiquity of concurrent data structure libraries and the intricacy of their designs, it is vital to develop methods and frameworks to increase confidence in their correctness. Linearizability ( Herlihy and Wing 1990 ) is the standard correctness criterion for concurrent libraries. It states that each library operation can be considered to be performed atomically at some point, called the linearization point, between its invocation and return. In this manner, linearizability makes each operation appear to “take effect” instantaneously while it preserves the order of non-concurrent operations. Linearizability allows client threads to understand the data structure in terms of atomic actions without considering the complications of concurrency. Since linearizability is the accepted correctness criterion for concurrent libraries, proving the latter’s correctness amounts to proving their linearizability. Static verification techniques for proving linearizability, such as model checking and theorem proving, suffer from scalability issues due to the complicated nature of library implementations typically involving unbounded data domains such as integers and counters and comprising dynamically evolving heaps ( Abdulla et al. 2018 ) . Due to these practical limitations of static methods, many researchers have developed complementary, dynamic techniques like testing and monitoring. In monitoring, we analyze the linearizability of only a single library history rather than all histories, which is the case for static verification frameworks. The goal is to obtain scalability by sacrificing completeness. In monitoring, we run the program, record a single history that it generates, and then check whether the recorded history is linearizable. In particular, we do not need to consider the underlying library implementation and avoid analyzing its complex state space. Monitoring offers several advantages. First, like other dynamic techniques, it increases confidence in the correctness of the implementation and provides eager detection of bugs that can lie deep in the program’s state space ( Emmi and Enea 2018 ) . Second, monitoring is scalable, allowing the analysis of histories with thousands of events. While incomplete, analyzing long histories still gives extensive state space coverage. Since we would like to analyze long histories, a monitoring algorithm’s time complexity must be low in the length of the input history. Linear time complexity is satisfied by several monitors designed for checking typical safety properties such as assertion validation ( Havelund and Rosu 2004 ) . In contrast, monitoring linearizability against arbitrary {\mathsf{ADT}} s requires exponential time ( Gibbons and Korach 1997 ) . This high complexity rules out practically scalable monitoring algorithms that cover general {\mathsf{ADT}} classes. One way to avoid the exponential time complexity is to develop algorithms for specific useful {\mathsf{ADT}} s such as stacks, queues, and sets. For instance, ( Emmi and Enea 2018 ) introduced a class of {\mathsf{ADT}} s, called collection types , that cover common {\mathsf{ADT}} s provided by libraries, e.g., java.util.concurrent , such as stacks, queues, sets, and maps. Other papers that provide polynomial monitoring algorithms include ( Emmi et al. 2015 ; Peterson et al. 2021 ) . While the problem seems simple, and the algorithms described in the above papers are elegant and efficient, the problem is more complex. Unfortunately, in the case of stacks and queues, previous polynomial algorithms either lack a correctness proof ( Emmi et al. 2015 ) (and the proof seems far from trivial), or the main correctness lemmas are erroneous ( Emmi and Enea 2018 ) (and how to fix them is not apparent to us), or the algorithms return incorrect responses for some inputs ( Peterson et al. 2021 ) . Thus, to our knowledge, polynomial time algorithms for monitoring stacks, queues, sets, or multisets have yet to be proven correct. This paper introduces monitoring algorithms with complexities {\mathcal{O}}(n^{2}) , {\mathcal{O}}(n\;log\,n) , and {\mathcal{O}}(n) , respectively, for stacks, queues, and (multi)sets, where n is the length of the input history. Our results for stacks and queues hold under the standard assumption of data-independence , i.e., the behavior of the library is not sensitive to the actual values stored in the stack or the queue ( Abdulla et al. 2013 ; Bouajjani et al. 2017 ; Wolper 1986 ) . On the other hand, it is not realistic to assume data independence for set and multiset algorithms, and we do not assume that either in our algorithms. We refer to Section 3.1.4 for more details about data-independence. The algorithms we provide for the different data structures use various and mutually different strategies. We provide a detailed overview of the main concepts and ideas in Section 3 . We decompose the structure of a linearization for each of the {\mathsf{ADT}} s considered. We note that the structure can be inductively defined for stacks, and we develop a recursive algorithm that matches this structure. For queues, we note that every unlinearizable history must have a critical pair , i.e., a set of two values of the history, the operations on which are unlinearizable. Finally, for sets and multisets,

Read the complete text