dc.contributor.author | Hadjimitsis, Leonidas | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.creator | Hadjimitsis, Leonidas | en |
dc.creator | Mavronicolas, Marios | en |
dc.date.accessioned | 2019-11-13T10:40:19Z | |
dc.date.available | 2019-11-13T10:40:19Z | |
dc.date.issued | 1998 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54059 | |
dc.description.abstract | Counting 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.publisher | ACM | en |
dc.source | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | en |
dc.source | Proceedings of the 1998 17th Annual ACM Symposium on Principles of Distributed Computing | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0031618462&partnerID=40&md5=d92201ee6e2caed6c2ee870d71f72987 | |
dc.subject | Multiprocessing systems | en |
dc.subject | Computer networks | en |
dc.subject | Data communication systems | en |
dc.subject | Concurrency control | en |
dc.subject | Counting networks | en |
dc.subject | Balancing networks | en |
dc.title | Contention in balancing networks resolved | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.description.startingpage | 41 | |
dc.description.endingpage | 50 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Conference Object | en |
dc.description.notes | <p>Sponsors: ACM | en |
dc.description.notes | Conference code: 48876</p> | en |