Concurrent counting

Our purpose is to implement clocks and, in general, counters in a shared memory environment. A concurrent counter is a counter that can be incremented and read, possibly at the same time by many processes. We study counters that achieve high level of concurrency and thus are likely to reduce memory contention; require only weak atomicity and thus are easy to implement; do not depend on the initial state of the memory and hence are more robust to memory changes; and are wait-free - one process cannot prevent another process from finishing its increment or read operations - and thus can tolerate any number of process failures. We concentrate on providing upper and lower bounds on the space complexity of the counters studied.