Public data structures: Counters as a special case

A public data structure is required to work correctly in a concurrent environment where many processes may try to access it, possibly at the same time. In implementing such a structure nothing can be assumed in advance about the number or the identities of the processes that might access it. While most of the known concurrent data structures are not public, there are few which are public. Interestingly, these public data structures all deal with various variants of counters, which are data structures that support two operations: increment and read. In this paper, we define the notion of a public data structure, and investigate several types of public counters. Then we give an optimal construction of public counters which satisfies a weak correctness condition, and show that there is no public counter which satisfies a stronger condition. It is hoped that this work will provide insights into the design of other, more complicated, public data structures.