Balancing networks: State of the art
Google Scholar check
MetadataShow full item record
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 resultscombinatorial properties of balancing networks have been uncovered, revealing a rich, underlying mathematical structurethe 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.