Small-depth counting networks
Michael Klugerman, C. Greg Plaxton · 1992
Generalizingthe notion of a sorting network, Aspnes, Herlihy, and Shavit recently introduced a class ofso-called "counting" networks, and established an 0(lg2n) upper bound on the depth complexity of such networks.Their work was motivated byanumberofpractical applications arising inthe domain of asynchronous shared memory machines.This paper continues the analysis of counting networks, providing a number of new upper bounds.In particular, we present an explicit construction of an O(c]g" ~lg n)depth counting network, a randomized construction of an O(lg n)-depth network (that works with extremely high probability), and using the random construction we present an existential proof of a deterministic o(lg n)-depth network, The latter result matches the trivial Q(lg n)-depth lower bound to within a constant factor.