Mindicators: A Scalable Approach to Quiescence

Abstract—We introduce the Mindicator, a new shared object that is optimized for querying the minimum value of a set of values proposed by several processes. A mindicator may hold at most one value per process. This interface is designed for use in shared memory runtime systems, such as garbage collectors, software transactional memory (TM), and operating system kernels. We introduce linearizable and relaxed mindicator im-plementations, both of which are lock-free. Our algorithms employ a tree structure, where querying the minimum element takes constant time, and adding and removing elements from the set does not hinder scalability. In microbenchmarks and a synthetic TM workload, we show that both provide good scalability on the x86 and SPARC platforms. Keywords-concurrent data structures; synchronization; lock-freedom; linearizability; I