TY - GEN
T1 - Supporting increment and decrement operations in balancing networks
AU - Aiello, William
AU - Busch, Costas
AU - Herlihy, Maurice
AU - Mavronicolas, Marios
AU - Shavit, Nir
AU - Touitou, Dan
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - 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 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.
AB - 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 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.
UR - http://www.scopus.com/inward/record.url?scp=32144455490&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=32144455490&partnerID=8YFLogxK
U2 - 10.1007/3-540-49116-3_37
DO - 10.1007/3-540-49116-3_37
M3 - Conference contribution
AN - SCOPUS:32144455490
SN - 354065691X
SN - 9783540656913
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 393
EP - 403
BT - STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Meinel, Christoph
A2 - Tison, Sophie
PB - Springer Verlag
T2 - 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999
Y2 - 4 March 1999 through 6 March 1999
ER -