James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the Association for Computing Machinery 41(5):1020–1048, September 1994. An earlier version appeared in Twenty-Third Annual ACM Symposium on Theory of Computing, May 1991, pp. 348–358, under the title “Counting networks and multiprocessor coordination.”
Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention.
Motivated by observations on the behavior of sorting networks, we offer a new approach to solving such problems, by introducing counting networks, a new class of networks that can be used to count. We give two counting network constructions, one of depth log n (1 + log n) / 2 using n log n (1 + log n) / 4 “gates” and a second of depth log² n, using n log² n / 2 gates. These networks avoid the sequential bottlenecks inherent to earlier solutions, and substantially lower the memory contention.
Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.
@article(AspnesHS1994,
title="Counting networks",
author="James Aspnes and Maurice Herlihy and Nir Shavit",
journal={Journal of the ACM},
volume=41,
number=5,
pages={1020--1048},
month=sep,
year=1994
)