Balancing networks: State of the art
Date
1997Author
Mavronicolas, MariosSource
Information SciencesVolume
97Issue
1-2Pages
125-157Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Balancing networks have recently been proposed by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 348-358 as a new class of distributed, low-contention data structures suitable for solving a variety of multiprocessor coordination problems that can be expressed as balancing problems. A significant amount of recent research in multiprocessor computing has been devoted to balancing networks. By way of sampling: constructions of balancing networks satisfying special-purpose properties have been presented and complemented by corresponding inconstructibility results combinatorial properties of balancing networks have been uncovered, revealing a rich, underlying mathematical structure the actual performance of balancing networks has been evaluated by both theoretical and experimental means under a variety of degrees of processor concurrency. In this work, I attempt to survey, exemplify, and unify recent research on balancing networks. © Elsevier Science Inc. 1997.