Counting networks with arbitrary fan-out

Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb₁,...,b_k, if there exists a prime factorp ofn, such thatp does not divideb_i, for alli, 1ik. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2^k, for any integerk0, is constructed out of 2-balancers andp-balancers.Eran Aharonson received the B.A. and M.Sc. degrees in Computer Science from the Technion, Israel Institute of Technology (Haifa, Israel) in 1989 and 1992, respectively. He is currently vice president for research and development at ART-Advanced Recognition Technolgies Ltd., a company dedicated to handwriting and voice recognition. His general research interests are distributed computation, theoretical computer science and pattern recognition.Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.A preliminary version of this paper appears in proceedings of the3rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992, pp. 104–113. This research was supported by Technion V.P.R.-B. and G. Greenberg Research Fund (Ottawa)Supported by Rashi Enterprise graduate fellowship