dc.contributor.author | Aiello, W. | en |
dc.contributor.author | Busch, Costas | en |
dc.contributor.author | Herlihy, M. | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Shavit, N. | en |
dc.contributor.author | Touitou, D. | en |
dc.contributor.editor | Tison S. | en |
dc.contributor.editor | Meinel C. | en |
dc.creator | Aiello, W. | en |
dc.creator | Busch, Costas | en |
dc.creator | Herlihy, M. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Shavit, N. | en |
dc.creator | Touitou, D. | en |
dc.date.accessioned | 2019-11-13T10:38:11Z | |
dc.date.available | 2019-11-13T10:38:11Z | |
dc.date.issued | 1999 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53505 | |
dc.description.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 [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. © Springer-Verlag Berlin Heidelberg 1999. | en |
dc.source | 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-32144455490&partnerID=40&md5=aae735f523f6793a802dc267f0f6a7c6 | |
dc.subject | Network management | en |
dc.subject | Concurrency control | en |
dc.subject | Application programs | en |
dc.subject | Boundedness properties | en |
dc.subject | Counting networks | en |
dc.subject | Distributed data structures | en |
dc.subject | In networks | en |
dc.subject | Input vector | en |
dc.subject | Novel concept | en |
dc.subject | Shared counters | en |
dc.title | Supporting increment and decrement operations in balancing networks | en |
dc.type | info:eu-repo/semantics/article | |
dc.description.volume | 1563 | |
dc.description.startingpage | 393 | |
dc.description.endingpage | 403 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Sponsors: | en |
dc.description.notes | Conference code: 148959 | en |
dc.description.notes | Cited By :7</p> | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | en |
dc.contributor.orcid | Busch, Costas [0000-0002-4381-4333] | |
dc.gnosis.orcid | 0000-0002-4381-4333 | |