A lower bound on wait-free counting
Shlomo Moran, Gadi Taubenfeld · 1993
A counting protocol (mod m) consists of shared memory bits -referred to as the counter -and of a procedure for incrementing the counter value by 1 (mod m).The procedure may be executed by many processes concurrently.It is required to satisfy a very weak correctness requirement, namely: the counter is required to show a correct value only in quiescent states -states in which no process is incrementing the counter.Special cases of counting protocols are "counting networks" [AHS91] and "concurrent counters" [MTY92].We consider the problem of implementing a wait-free counting protocol, assuming that the basic atomic operation of a process is a read-modify-write on a single bit.Let ~lip(.%)be the maximum number of times a single increment operation changes the counter bits in a counting protocol Pr.Our main result is: In any waitfree counting protocol Pr which counts modulo m, m divides 2f~@tp'J.Thus, flip(Pr) z log m and m is a power of 2. This result provides interesting generalizations of lower bounds and impossibility results for counting and smoothing networks, Recently there was much interest in the implementation of counters in a concurrent environment where many processes may try to access the