# Technical Report CS0679

 TR#: CS0679 Class: CS Title: COUNTING NETWORKS WITH ARBITRARY FAN-OUT Authors: E. Aharonson and H. Attiya PDF - Revised CS0679.revised.pdf PDF - Revised again CS0679.revised2.pdf Abstract: It is shown that an acyclic smooting network (and hence counting network) of fan-out $n$ cannot be constructed from balancers of fan-out $b_{1},...,b_{k}$, if there exists a prime factor $p$ of $n$, such that $p$ does not divide $b_{i}$, for all $i, 1 \leq i \leq k$. This holds regardless of the depth of the network, as long as it is finite. In particular, only smoothing networks of fan-out $2^{\ell}$ (for a non-negative integer $\ell$ ) can be constructed out of 2-balancers. A very simple construction of {\em cyclic} counting networks with fan-out $n$ is presented. Proving the correctness of this construction involves a novel technique of arguing about counting networks in non-quiescent states. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0679), rather than to the URL of the PDF files directly. The latter URLs may change without notice.