Chicago Journal of Theoretical Computer Science

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

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.

DOI: 10.4086/cjtcs.2000.004
[] Article 3
[back] Volume 2000 [back] Published articles
[CJCTS home]

Last modified: Thurs Feb 15 2001