Upper Bounds for Boundless Tagging with Bounded Objects

A fundamental technique used in the design of shared memory algorithms is tagging, where registers or other shared objects get augmented with additional values, called tags. In this paper, we provide a framework for tagging, and prove upper bounds for the complexity of this problem. We define new types that allow processes to generate tags infinitely often, store them to or retrieve them from other objects, use them safely, and release them when they are not needed any more. We present asymptotically optimally time efficient implementations of those types from objects of bounded size. In particular, our tags need only objects of logarithmic size, and operations on them can be performed in constant step complexity. In addition to the straightforward applications that use tags directly, our implementations can also be used for memory reclamation in a number of algorithms, such as those based on single compare-and-swap universal or read-copy-update.