Counting networks are a class of distributed data structures that support highly concurrent implementations of shared
Fetch&Increment counters. Applications of these counters include shared pools and stacks, load balancing, and software barriers [
4,
12,
13,
18]. A limitation of counting networks is that the resulting shared counters can be incremented, but not decremented.
A recent result by Shavit and Touitou [18] showed that the subclass of tree-shaped counting networks can support, in addition, decrement operations. This paper generalizes
their result, showing that any counting network can be extended to support atomic decrements in a simple and natural way. Moreover, it is shown that decrement
operations can be supported in networks that provide weaker properties, such as K-smoothing. In general, we identify a broad class of properties, which we call boundedness properties, that are preserved by the introduction of decrements: if a balancing network satisfies a particular boundedness property
for increments alone, then it continues to satisfy that property for both increments and decrements.
Our proofs are purely combinatorial and rely on the novel concept of a fooling pair of input vectors.
This paper combines, unifies, and extends results appearing in preliminary form in [2] and [6].
Partially supported by funds for the promotion of research at University of Cyprus. Part of the work of this author was performed
while at AT&T Labs - Research, Florham Park, NJ, as a visitor to the Special Year on Networks, DIMACS Center for Discrete
Mathematics and Theoretical Computer Science, Piscataway, NJ.