A combinatorial treatment of balancing networks
Date
1996Source
Journal of the ACMVolume
43Issue
5Pages
794-839Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures suitable for solving many fundamental multi-processor coordination problems that can be expressed as balancing problems. In this work, we present a mathematical study of the combinatorial structure of balancing networks, and a variety of its applications. Our study identifies important combinatorial transfer parameters of balancing networks. In turn, necessary and sufficient combinatorial conditions are established, expressed in terms of transfer parameters, which precisely characterize many important and well studied classes of balancing networks such as counting networks and smoothing networks. We propose these combinatorial conditions to be "balancing analogs" of the well known Zero-One principle holding for sorting networks. Within the combinatorial framework we develop, our first application is in deriving combinatorial conditions, involving the transfer parameters, which precisely delimit the boundary between counting networks and sorting networks.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Doctoral Thesis Open Access
KSPOT : a network-aware framework for energy-efficient data acquisition in wireless sensor networks
Andreou, Panayiotis G. (Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών / University of Cyprus, Faculty of Pure and Applied Sciences, 2011-06)Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούνται από μικροσκοπικές συσκευές με περιορισμένους πόρους και παρέχουν στους χρήστες την ευκαιρία να παρακολουθούν το περιβάλλον με πολύ ψηλή ευκρίνεια. Για τη συλλογή των δεδομένων ...
-
Article
A network-aware framework for energy-efficient data acquisition in wireless sensor networks
Andreou, Panayiotis G.; Zeinalipour-Yazdi, Constantinos D.; Samaras, George S.; Chrysanthis, Panos K. (2014)Wireless sensor networks enable users to monitor the physical world at an extremely high fidelity. In order to collect the data generated by these tiny-scale devices, the data management community has proposed the utilization ...
-
Article
Adaptive network-aided session support in context-aware converged mobile networks
Antoniou, Josephina; Christophorou, C.; Simoes, J.; Pitsillides, Andreas (2012)The increase of networking complexity requires the design of new performance optimisation schemes for delivering sessions to users under different conditions. This paper addresses context-aware, adaptive multiparty sessions ...