2014/02/17 by Radha Jagadeesan, Jagadeesan, Radha, James Riely +1
Computer Science · #Advanced Data Storage Technologies #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #cs.PL
paper · pdf · doi:10.48550/arxiv.1402.4043
Short version in ICALP 2014. http://icalp2014.itu.dk/
openalex publication_date 2014/02/17 · arxiv created 2014/04/26 · arxiv updated 2014/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Linearizability is the de facto correctness criterion for concurrent data structures. Unfortunately, linearizability imposes a performance penalty which scales linearly in the number of contending threads. Quiescent consistency is an alternative criterion which guarantees that a concurrent data structure behaves correctly when accessed sequentially. Yet quiescent consistency says very little about executions that have any contention. We define quantitative quiescent consistency (QQC), a relaxation of linearizability where the degree of relaxation is proportional to the degree of contention. When quiescent, no relaxation is allowed, and therefore QQC refines quiescent consistency, unlike other proposed relaxations of linearizability. We show that high performance counters and stacks designed to satisfy quiescent consistency continue to satisfy QQC. The precise assumptions under which QQC holds provides fresh insight on these structures. To demonstrate the robustness of QQC, we provide three natural characterizations and prove compositionality.