A combinatorial treatment of balancing networks
SourceJournal of the ACM
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Kyriacou, Costas; Evripidou, Paraskevas (1999)This paper presents the network interface for the Data Driven Network Of Workstations (DzNOW), a multithreaded architecture that uses the decoupled data driven model of execution. D2NOW is built using commodity workstations. ...
Double Networks Based on Amphiphilic Cross-Linked Star Block Copolymer First Conetworks and Randomly Cross-Linked Hydrophilic Second Networks Rikkou-Kalourkoti, Maria D.; Kitiri, E. N.; Patrickios, Costas S.; Leontidis, Epameinondas; Constantinou, Martha; Constantinides, G.; Zhang, X. K.; Papadakis, Christine M. (2016)This study presents the preparation and characterization of double networks (DN) based on a first amphiphilic polymethacrylate conetwork (APCN) and a second polyacrylamide network. The APCN first network comprised ...
Synthesis and characterization of robust double-networks based on end-linked, pH-responsive first networks Kitiri, Elina N.; Rikkou-Kalourkoti, Maria D.; Sophocleous, Manolia; Patrickios, Costas S. (2015)Abstract Fragile, end-linked hydrophilic tertiary amine based methacrylate (first) networks were mechanically reinforced using the double-network principle, via the introduction of a polyacrylamide second network. Reinforcement ...