Threshold counters with increments and decrements

A threshold counter is a shared data structure that assumes integer values. It provides two operations: changes the current counter value from v to v+1, while returns the value v/w, where v is the current counter value and w is a fixed constant. Thus, the operation returns the “approximate” value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a operation that changes the counter value from v to v?1.