Show simple item record

dc.contributor.authorAiello, W.en
dc.contributor.authorBusch, Costasen
dc.contributor.authorHerlihy, M.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorShavit, N.en
dc.contributor.authorTouitou, D.en
dc.contributor.editorTison S.en
dc.contributor.editorMeinel C.en
dc.creatorAiello, W.en
dc.creatorBusch, Costasen
dc.creatorHerlihy, M.en
dc.creatorMavronicolas, Mariosen
dc.creatorShavit, N.en
dc.creatorTouitou, D.en
dc.date.accessioned2019-11-13T10:38:11Z
dc.date.available2019-11-13T10:38:11Z
dc.date.issued1999
dc.identifier.issn0302-9743
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/53505
dc.description.abstractCounting 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.source16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999en
dc.source.urihttps://www.scopus.com/inward/record.uri?eid=2-s2.0-32144455490&partnerID=40&md5=aae735f523f6793a802dc267f0f6a7c6
dc.subjectNetwork managementen
dc.subjectConcurrency controlen
dc.subjectApplication programsen
dc.subjectBoundedness propertiesen
dc.subjectCounting networksen
dc.subjectDistributed data structuresen
dc.subjectIn networksen
dc.subjectInput vectoren
dc.subjectNovel concepten
dc.subjectShared countersen
dc.titleSupporting increment and decrement operations in balancing networksen
dc.typeinfo:eu-repo/semantics/article
dc.description.volume1563
dc.description.startingpage393
dc.description.endingpage403
dc.author.faculty002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences
dc.author.departmentΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeArticleen
dc.description.notes<p>Sponsors:en
dc.description.notesConference code: 148959en
dc.description.notesCited By :7</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en
dc.contributor.orcidBusch, Costas [0000-0002-4381-4333]
dc.gnosis.orcid0000-0002-4381-4333


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record