AbstractBalancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represented 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.
We next turn to use the necessity of the shown combinatorial conditions in deriving width inconstructibility results and lower bounds on depth-like measures for several classes of balancing networks; these results significantly improve upon previous ones shown by Aharonson and Attiya (Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 104-113, January 1992), and Moran and Taubenfeld (Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, pp. 251-259, August 1993) in terms of strength, generality, and proof simplicity.
The sufficiency of the shown combinatorial conditions is employed in designing the first formal algorithms for mathematically verifying that a given network belongs to each of a collection of classes. These algorithms are simple, modular and easy to implement, consisting merely of multiplying matrices and evaluating matricial functions.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: Costas Busch and Marios Mavronicolas. A combinatorial treatment of balancing networks. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 206-215, Los Angeles, California, 14-17 August 1994.
Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design -- distributed networks, network topology; C.2.4 [Computer-Communication Networks]: Distributed Systems -- distributed applications; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sorting and searching; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms, counting problems; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, networks problems
General Terms: Theory, Verification, Algorithms
Additional Key Words and Phrases: Balancing networks, block-input networks, block-output networks, combinatorial characterizations, counting networks, impossibility results, incidence matrices, smoothing networks, transfer parameters
Selected papers that cite this one
- Costas Busch and Marios Mavronicolas. Impossibility results for weak threshold networks. Information Processing Letters, 63(2):85-90, 28 July 1997.
Selected references
- James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the ACM, 41(5):1020-1048, September 1994.
- James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks and multi-processor coordination. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 348-358, New Orleans, Louisiana, 6-8 May 1991.
- Martin Dowd, Yehoshua Perl, Larry Rudolph, and Michael Saks. The periodic balanced sorting network. Journal of the ACM, 36(4):738-757, October 1989.
- Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 174-183, San Diego, California, 16-18 May 1993.
- Allan Gottlieb, Boris D. Lubachevsky, and Larry Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Transactions on Programming Languages and Systems, 5(2):164-189, April 1983.
- Maurice Herlihy, Nir Shavit, and Orli Waarts. Low contention linearizable counting. In 32nd Annual Symposium on Foundations of Computer Science, pages 526-535, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Michael Klugerman and C. Greg Plaxton. Small-depth counting networks. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 417-428, Victoria, British Columbia, Canada, 4-6 May 1992.
- Miros{\l}aw Kuty{\l}owski, Krzysztof Lory\'s, Brigitte Oesterdiekhoff, and Rolf Wanka. Fast and feasible periodic sorting networks of constant depth. In 35th Annual Symposium on Foundations of Computer Science, pages 369-380, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Ian Parberry. Single-exception sorting networks and the computational complexity of optimal sorting network verification. Mathematical Systems Theory, 23(2):81-93, 1990.
- David Peleg and Eli Upfal. The token distribution problem. SIAM Journal on Computing, 18(2):229-243, April 1989.