Volume 2000
Article 4
Published by MIT Press. Copyright 2000 Massachusetts Institute of
Technology.
Your institution may already be a
subscriber to CJTCS. If not,
please subscribe
for legitimate access to all journal articles.
Supporting Increment and Decrement Operations
in Balancing Networks
William Aiello (ATT Laboratories), Costas Busch (Brown University), Maurice Herlihy (Brown University),
Marios Mavronicolas (University of Cyprus), Nir Shavit (Tel-Aviv University and MIT),
and Dan Touitou (IDC Herzliya, Israel).
7 December 1998
Abstract
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. 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 both increment and decrement
operations. In this paper we generalize their result, showing that
any counting network can be extended to support atomic
decrements in a simple and natural way. Moreover, we identify a broad
class of network boundedness properties, that, like the counting
property, 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.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 3
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2000
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}