Show simple item record

dc.contributor.authorHadjimitsis, Leonidasen
dc.contributor.authorMavronicolas, Mariosen
dc.creatorHadjimitsis, Leonidasen
dc.creatorMavronicolas, Mariosen
dc.description.abstractCounting networks have been originally presented by Aspnes et al. as a new class of distributed/coordinated data structures suitable for solving many fundamental, multi-processor coordination problems that can be expressed as counting problems. The motivation for introducing counting networks has been to implement shared counters in a way to outperform, in terms of contention, conventional, single-variable solutions at high levels of processor concurrency. Although several specific constructions of counting networks have so far been shown to incur low amortized contention, the fundamental question of whether counting networks in general so do has yet remained unresolved. In this work, we use elegant, yet intuitive and simple, combinatorial arguments to settle this question in the positive. We show the unexpected result that, in fact, any balancing network of width w and depth d incurs an amortized contention of Θ(nd/w) at processor concurrency n. This holds whether or not the balancing network is counting, and whether or not it possesses any kind of smoothing property. Thus, a significant implication of our work is that contention in balancing networks is not related to any other than their most basic structural properties. Our combinatorial arguments are drawn from a study of the combinatorial structure of balancing networks due to Busch and Mavronicolas.en
dc.sourceProceedings of the Annual ACM Symposium on Principles of Distributed Computingen
dc.sourceProceedings of the 1998 17th Annual ACM Symposium on Principles of Distributed Computingen
dc.subjectMultiprocessing systemsen
dc.subjectComputer networksen
dc.subjectData communication systemsen
dc.subjectConcurrency controlen
dc.subjectCounting networksen
dc.subjectBalancing networksen
dc.titleContention in balancing networks resolveden
dc.description.endingpage50 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Sponsors: ACMen
dc.description.notesConference code: 48876</p>en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record