\documentclass[11pt]{article} \newcommand{\remove}[1]{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Theorems %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{conjecture}{Conjecture}[section] \newtheorem{definition}{Definition}[section] \newtheorem{observation}{Observation}[section] \newtheorem{example}{Example}[section] % to get nice proofs ... \newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}} \newenvironment{proof}{\begin{trivlist} \item[\hspace{\labelsep}{\bf\noindent Proof: }] }{\qedsymb\end{trivlist}} \newenvironment{proofsketch}{\begin{trivlist} \item[\hspace{\labelsep}{\bf\noindent Sketch of proof: }] }{\qedsymb\end{trivlist}} \newcommand{\qed}{\hfill\rule{2mm}{2mm}} \newenvironment{remark}{\begin{trivlist} \item[\hspace{\labelsep}{\bf\noindent Remark. }]}{\end{trivlist}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Math Expressions %%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\etal}{{\it et al.}\ } \newcommand{\divd}{~\mbox{div}~} \newcommand{\mod}{~\mbox{mod}~} \newcommand{\state}{\mbox{state}} \newcommand{\depth}{\mbox{depth}} \newcommand{\fin}{f_{\rm{in}}} \newcommand{\fout}{f_{\rm{out}}} \newcommand{\win}{w_{\rm{in}}} \newcommand{\wout}{w_{\rm{out}}} \newcommand{\Wout}{W_{\rm{out}}} \newcommand{\wmed}{w_{\rm{med}}} \newcommand{\x}[2]{{\bf x}_{#1}^{(#2)}} \newcommand{\tx}[2]{\tilde{{\bf x}}_{#1}^{(#2)}} \newcommand{\y}[2]{{\bf y}_{#1}^{(#2)}} \newcommand{\z}[2]{{\bf z}_{#1}^{(#2)}} \newcommand{\ax}[1]{\x{#1}{\fin}} \newcommand{\ay}[1]{\y{#1}{\fout}} \newcommand{\ao}{{\bf r}^{(\fout)}} \newcommand{\aone}{{\bf 1}^{(\fout)}} \newcommand{\azeroin}{{\bf 0}^{(\fin)}} \newcommand{\azeroout}{{\bf 0}^{(\fout)}} \newcommand{\bx}[1]{\x{#1}{\win}} \newcommand{\tbx}[1]{\tx{#1}{\win}} \newcommand{\by}[1]{\y{#1}{\wout}} \newcommand{\bz}[1]{\z{#1}{\wmed}} \newcommand{\bxw}[1]{\x{#1}{w}} \newcommand{\byw}[1]{\y{#1}{w}} \newcommand{\bzw}[1]{\z{#1}{w}} \newcommand{\bzeroin}{{\bf 0}^{(\win)}} \newcommand{\bzeroout}{{\bf 0}^{(\wout)}} \newcommand{\bzeromed}{{\bf 0}^{(\wmed)}} \newcommand{\B}{{\cal B}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% DOCUMENT %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \title{Supporting Increment and Decrement Operations in Balancing Networks\footnotemark[1]} \author{ William Aiello\footnotemark[2] \and Costas Busch\footnotemark[3] \and Maurice Herlihy\footnotemark[3] \and Marios Mavronicolas\footnotemark[4] \and Nir Shavit\footnotemark[5] \and Dan Touitou\footnotemark[6] } \footnotetext[1]{ This paper combines, unifies, and extends results appearing in preliminary form in~\cite{AHST95} and~\cite{BM96}. A preliminary version of this paper appears in the {\it Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science ({STACS}'99),} pp. 377--386, Trier, Germany, March 1999.} \footnotetext[2]{ AT\&T Labs, 180 Park Avenue, Florham Park, NJ 07932. Email: {\tt aiello@research.att.com} } \footnotetext[3]{ Department of Computer Science, Brown University, Providence, RI 02915. Email: {\tt \{cb,mph\}@cs.brown.edu} } \footnotetext[4]{ Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus. Partially supported by funds for the promotion of research at University of Cyprus. Part of the work of this author was performed while at AT\&T Labs -- Research, Florham Park, NJ, as a visitor to the Special Year on Networks, DIMACS Center for Discrete Mathematics and Theoretical Computer Science, Piscataway, NJ. Email: {\tt mavronic@cs.ucy.ac.cy} } \footnotetext[5]{ Department of Computer Science, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel, and Massachusetts Institute of Technology, Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139. Research supported by Israel Science Foundation under grant 03610882, the Israeli Ministry of Science, and NSF grants 9225124-CCR and 9520298-CCR Email: {\tt shanir@theory.lcs.mit.edu} } \footnotetext[6]{ IDC Herzliya, Tel-Aviv, Israel. Email: {\tt danidin@math.tau.ac.il} } \maketitle \begin{abstract} {\em Counting networks} are a class of distributed data structures that support highly concurrent implementations of shared {\it Fetch\&Increment} counters. Applications of these counters include shared pools and stacks, load balancing, and software barriers. A limitation of counting networks is that the resulting shared counters can be incremented, but not decremented. A recent result by Shavit and Touitou showed that the subclass of tree-shaped counting networks can support both increment and decrement operations. In this paper we generalize their result, showing that {\em any} counting network can be extended to support atomic decrements in a simple and natural way. Moreover, we identify a broad class of network {\em boundedness properties,} that, like the counting property, are preserved by the introduction of decrements: if a balancing network satisfies a particular boundedness property for increments alone, then it continues to satisfy that property for both increments and decrements. %Our proofs are purely combinatorial and rely on the introduction of the %novel concept of a {\em fooling pair} of input vectors. \end{abstract} %===================================== %===================================== \section{Introduction} \label{introduction} \subsection{Motivation-Overview} \label{motivation overview} {\em Counting networks} were originally introduced by Aspnes {\em et al.}~\cite{AHS91} and subsequently extended in~\cite{AA92,FLL93,HKM93}. They are designed to provide highly concurrent implementations of shared {\it Fetch\&Increment} counters, shared pools and stacks, load balancing modules, and software barriers (see, e.g.,~\cite{AHS91,HLS95,KM96,ST95}). Counting networks are constructed from basic computing elements called {\em balancers}. On an abstract level, a balancer can be thought of as a routing switch for elements called {\em tokens}. It has a collection of input wires and a collection of output wires, respectively called the balancer's {\em fan-in} and {\em fan-out}. Tokens arrive asynchronously on arbitrary input wires, and are routed to successive output wires in a ``round-robin'' fashion. If one thinks of a balancer as having a ``toggle'' variable tracking which output wire the next token should exit on, then a token traversal amounts to a {\it Fetch\&Toggle} operation, retrieving the value of the output wire and changing the toggle state to point to the next wire. The distribution of tokens on the output wires of a balancer thus satisfies the {\em step property}~\cite{AHS91}: if $y_i$ tokens exit on output wire $i$, then $0 \leq y_i - y_j \leq 1$ for any $j > i$. A {\em balancing network} is a network of balancers, constructed by connecting balancers' output wires with other balancers' input wires in an acyclic fashion, in a way similar to the way {\em comparator networks} are constructed from {\em comparators}~\cite[Chapter 28]{CLR90}. The network itself has a number of input and output wires. A token enters the network on an input wire, traverses a sequence of balancers, and exits on an output wire. A balancing network is a {\em $K$-smoothing network}~\cite{AA92,AHS91} if, when all tokens have exited the network, the difference between the maximum and minimum number of tokens that exit on any output wire is bounded by $K$, regardless of the distribution of input tokens. Smoothing networks can be used for distributed load balancing. A $1$-smoothing network is a {\em counting network} if it satisfies the same step property as a balancer: when all tokens have traversed the network, if $y_i$ tokens exit on output wire $i$, then $0 \leq y_i - y_j \leq 1$ for any $j > i$. Counting networks can be used to implement {\it Fetch\&Increment} counters: the $l$-th token (where $l = 0,1,\ldots$) to exit on output wire $j$ returns the value $j + l \cdot \wout$, where $\wout$ is the network's fan-out. A limitation of counting networks is that they support increments but not decrements. Many synchronization algorithms and tools require the ability to decrement shared objects. For example, the classical synchronization constructs of {\em semaphores}~\cite{D65a}, {\em critical-regions}~\cite{HP72}, and {\em monitors}~\cite{B73} all rely on applying both increment and decrement operations on shared counters for both correctness and efficiency (see, e.g.,~\cite[Chapter 6]{SG94}). Moreover, several concurrent algorithms for classical multiprocessor synchronization problems such as the {\em mutual exclusion problem}~\cite{D65b} and the {\em readers-writers problem}~\cite{CHP71}, involve coordination by incrementing and decrementing of shared counters. Shavit and Touitou~\cite{ST95} provided the first counting network algorithm to support decrements for the class of networks that have the layout of a binary tree. They did so by introducing a new type of token for the decrement operation, which they named the {\em antitoken}.\footnote{The name was actually suggested by Yehuda Afek (personal communication).} Unlike a token, which traverses a balancer by fetching the toggle value and then advancing it, an antitoken sets the toggle back and then fetches it. Informally, an antitoken ``cancels'' the effect of the most recent token on the balancer's toggle state, and vice versa. In the same paper, Shavit and Touitou introduced the {\em gap step property,} as an extension to the step property correctness criterion for counting networks, intended to capture correctness when there are both tokens and antitokens traversing the network. They provide an operational proof that {\em counting trees}~\cite{SZ96} satisfy the gap step property when traversed by tokens and antitokens. Shavit and Touitou~\cite{ST95} also introduced the notion of ``elimination,'' which, they show, can be used to implement a highly concurrent ``pool'' or ``stack'' of items using a counting tree. This is done by having each token represent an enqueue operation, and each antitoken represent a dequeue operation. If a token and an antitoken meet at a balancer in the counting tree, they can ``eliminate'' one another; that is, the process shepherding the token can hand the value to the process shepherding the antitoken, and both processes can exit without need to traverse the rest of the tree. Even with ``elimination,'' the counting tree still preserves the desired gap step property. It is natural to ask whether the same properties hold for {\em arbitrary} counting networks. \footnote{This is especially so since efficient (low contention) implementations of tree-shaped counting networks require the use of randomized ``diffraction'' mechnisms~\cite{SZ96}, which cannot be ``hardwired.'' Having a hardwired (fixed layout) network is significant for hardware implementations, and for systems with real-time constraints.} More generally, what properties of balancing networks are preserved by the introduction of antitokens? In this paper, we give the first general answer to this question. We show the following results. \begin{itemize} \item If a balancing network is a counting network when inputs are tokens, then it remains a counting network when inputs include both tokens and antitokens. This result implies that {\em any} counting network can be extended to support a {\it Fetch\&Decrement} operation. \item Any counting network, not just elimination trees, permits tokens and antitokens to eliminate one another when implementing a concurrent pool. \item If a balancing network is a $K$-smoothing network when inputs are tokens, then it remains a $K$-smoothing network when inputs include both tokens and antitokens. \item More generally, we identify a broad class of properties, which we call {\em boundedness properties,} that are preserved by the introduction of antitokens: if a balancing network satisfies a particular boundedness property when inputs are tokens, then it continues to satisfy that property when inputs include both tokens and antitokens. The step property and the $K$-smoothing property are examples of boundedness properties. \end{itemize} An interesting aspect of our work is that, unlike \cite{ST95}, our proofs are combinatorial, not operational. They rely on the novel concept of a {\em fooling pair} of input vectors, which we believe is of independent interest. \subsection{Our Techniques and Main Result} \label{techniques and results} Aspnes {\em et al.}~\cite{AHS91} introduced the convention of assigning the value 1 to each token, a convention maintained by later constructions~\cite{AA92,BHM94,BM98,FLL93,HKM93,K94,KP92,SZ96}. Shavit and Touitou~\cite{ST95} assigned the value 1 to both tokens and antitokens, while embedding the cancelling nature of antitokens in the gap step property. Here, however, it is convenient to assign the value -1 to each antitoken, and 1 to each token. Generalizing the approach taken by Aspnes {\em et al.}~\cite{AHS91}, we represent a balancer as an ``operator'' carrying an integer {\em input vector} to an integer {\em output vector}. The $i$-th entry in the input vector represents the {\em algebraic sum} of tokens and antitokens received on the $i$-th input wire, and similarly for the output vector. For example, if this value is zero, then the same number of tokens and antitokens have arrived on that wire. In the original definition of counting networks, which permitted only tokens, all such values were non-negative. We treat a balancing network in the same way, as an ``operator'' on integer vectors. We show that any balancing network satisfying the step property for non-negative, integer input vectors, also satisfies the step property for arbitrary integer input vectors. implying that any counting network can be extended to support decrements. Moreover, we show that any balancing network that satisfies the $K$-smoothing property for non-negative, integer input vectors, satisfies the same property for arbitrary integer input vectors. In fact, we show the following general result. Think of a set of possible output vectors as defining a {\em property} of a balancing network. A {\em boundedness property} satisfies two conditions: \begin{itemize} \item it is a subset of the $K$-smoothing property, for some $K \geq 1$, and \item it is closed under the addition of any {\em constant} vector. \end{itemize} Both the $K$-smoothing and the step property are examples of boundedness properties. Our principal result is that any balancing network that satisfies a boundedness property when its input vector consists only of non-negative integers, %it will continue to satisfy that boundedness property even when its input vector consists of arbitrary integers. To prove our result, we introduce the concept of a fooling pair of input vectors. Let the {\em state} of any given balancer, viewed as a toggle mechanism, be the ``position'' of its toggle. Two input vectors are a {\em fooling pair} to any given balancer if they transition the balancer, starting from the initial state, to identical states. The state of a balancing network is defined as the collection of the states of its balancers. Naturally, two input vectors are a {\em fooling pair} to the balancing network if they transition it, starting from the initial state, to identical states. Fooling pairs partition the set of input vectors to equivalence classes according to which state they transition the network. An interesting equivalence class is the one in which the input vectors transition the network to a state identical to the initial state. We call the input vectors of this equivalence class {\em null vectors}. We establish interesting combinatorial properties of fooling pairs and null vectors. Roughly speaking, we prove our main equivalence result as follows. Consider any balancing network with some boundedness property; take any arbitrary, integer input vector and a corresponding integer output vector. By adding to the input vector an appropriate null vector, we obtain a new input vector such that all of its entries are non-negative integers. We show that the output vector corresponding to the new input vector is, in fact, equal to the original output vector plus a constant vector. Hence, our main equivalence result follows from closure of the boundedness property under addition with a constant vector. The rest of this paper is organized as follows. Section~\ref{framework} provides a framework for our discussion. In Section~\ref{remarks} we give a simple proof of our main result for a special class of balancing networks that we call ``regular'' networks, and we explain why this proof doesn't work for the general case of balancing networks. Fooling pairs, and their properties are treated in Section~\ref{fooling pairs}, and null vectors are treated in Section~\ref{null vectors}. Section~\ref{equivalence result} presents our main result. We conclude in Section~\ref{conclusion} with a discussion and some open problems. (In Appendices~\ref{fooling pairs -- appendix} and~\ref{null vectors -- appendix}, you can find some additional properties for fooling pairs and null vectors which are of general interest.) %===================================== %===================================== \section{Framework} \label{framework} In this section, we present some general definitions, which extend those in~\cite{AA92,BM98,FLL93,HKM93} to account for both tokens and antitokens; they somehow simplify and formalize corresponding ones in~\cite{ST95}. It is organized as follows. Subsection~\ref{notation} specifies some notation. Balancers and balancing networks are introduced in Subsections~\ref{balancers} and~\ref{balancing networks}, respectively. Sectionsection~\ref{boundedness properties} treats boundedness properties. \subsection{Notation} \label{notation} For any integer $g \geq 2$, ${\bf x}^{(g)}$ denotes the vector $\langle x_{0}, x_{1}, \ldots, x_{g-1} \rangle^{{\rm T}}$. For any vector ${\bf x}^{(g)}$, denote $\| {\bf x}^{(g)}\|_{1} = \sum_{i = 0}^{g-1} x_{i}$. We use ${\bf 0}^{(g)}$ to denote $\langle 0, 0, \ldots, 0 \rangle^{{\rm T}}$, a vector with $g$ zero entries. A {\em constant vector} is any vector in which each entry is equal to some constant $c$. We say that a vector is {\em non-negative} if all of its entries are non-negative integers. For any integer $x$ and positive integer $\delta$, denote $x \divd \delta$ and $x \mod \delta$ the integer quotient and remainder, respectively, of the division of $x$ by $\delta$; note that $0 \leq x \mod \delta \leq \delta - 1$ and $x = (x \divd \delta)\, \delta + x \mod \delta$. Say that {\em $\delta$ divides vector ${\bf x}^{(g)}$} if $\delta$ divides each entry of ${\bf x}^{(g)}$ (without leaving remainder). \subsection{Balancers} \label{balancers} Balancing networks are constructed from acyclically wired elements, called balancers, that route {\em tokens} and {\em antitokens} through the network, and {\em wires}. For the sake of generality, our balancers are defined as ``multibalancers,'' in the style of Aharonson and Attiya~\cite{AA92}, Felten {\em et al.}~\cite{FLL93}, and Hardavellas {\em et al.}~\cite{HKM93}; however, we follow Shavit and Touitou~\cite{ST95} to insist that our balancers handle both tokens and antitokens. We think of a token and an antitoken as the basic ``positive'' and ``negative'' units that are routed through the network. For any pair of positive integers $\fin$ and $\fout$, an {\em $(\fin, \fout)$-balancer,} or {\em balancer} for short, is a routing element receiving tokens and antitokens on $\fin$ input wires, numbered $0, 1, \ldots, \fin-1$, and sending out tokens and antitokens to $\fout$ output wires, numbered $0, 1, \ldots, \fout-1$; $\fin$ and $\fout$ are called the balancer's {\em fan-in} and {\em fan-out,} respectively. Tokens and antitokens arrive on the balancer's input wires at arbitrary times, and leave on its output wires. Roughly speaking, a balancer acts like a ``generalized'' {\em toggle,} which, on a stream of input tokens and antitokens, alternately forwards them to its output wires, going either down or up on each input token and antitoken, respectively. For clarity, we assume that all tokens and antitokens are distinct. Figure~\ref{figure:balancer} depicts a balancer with three input wires and five output wires, stretched horizontally; the balancer is stretched vertically. \begin{figure}[tp] \begin{center} %\input{bal_3x5.latex} \setlength{\unitlength}{2368sp}% % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \begin{picture}(7895,2854)(2906,-5555) \thinlines \put(4801,-3061){\circle*{140}} \put(4801,-3661){\circle*{140}} \put(4801,-4261){\circle*{140}} \put(4801,-4861){\circle*{140}} \put(4801,-5461){\circle*{140}} \thicklines \put(3001,-3661){\circle{160}} \thinlines \put(3601,-3061){\circle*{160}} \thicklines \put(3901,-3661){\circle{160}} \put(3601,-3661){\circle{160}} \thinlines \put(3301,-3661){\circle*{160}} \thicklines \put(3601,-4261){\circle{160}} \thinlines \put(3901,-4261){\circle*{160}} \put(5701,-3061){\circle*{160}} \thicklines \put(6001,-3061){\circle{160}} \put(5701,-5461){\circle{160}} \thinlines \put(6001,-5461){\circle*{160}} \thicklines \put(6301,-5461){\circle{160}} \put(5701,-4861){\circle{160}} \thinlines \put(6001,-4861){\circle*{160}} \thicklines \put(6301,-4861){\circle{160}} \put(5701,-4261){\circle{160}} \thinlines \put(9901,-4861){\circle*{140}} \put(9901,-5461){\circle*{140}} \put(9901,-4261){\circle*{140}} \put(9901,-3661){\circle*{140}} \put(9901,-3061){\circle*{140}} \thicklines \put(3901,-3061){\circle{160}} \put(3301,-3061){\circle{160}} \thinlines \special{ps: gsave 0 0 0 setrgbcolor}\put(4201,-3061){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4201,-3661){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4201,-4261){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4801,-4861){\line( 1, 0){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4801,-5461){\line( 1, 0){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9301,-3061){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9301,-3661){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9301,-4261){\line( 1, 0){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9901,-4861){\line( 1, 0){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9901,-5461){\line( 1, 0){600}} \special{ps: grestore}\thicklines \special{ps: gsave 0 0 0 setrgbcolor}\put(4801,-3061){\line( 0,-1){2400}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9901,-3061){\line( 0,-1){2400}} \special{ps: grestore}\put(3901,-4111){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}1\special{ps: grestore}}}} \put(3901,-3511){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}2\special{ps: grestore}}}} \put(3601,-3511){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}3\special{ps: grestore}}}} \put(3301,-3511){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}4\special{ps: grestore}}}} \put(3601,-2911){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}7\special{ps: grestore}}}} \put(3601,-4111){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}6\special{ps: grestore}}}} \put(3301,-2911){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}8\special{ps: grestore}}}} \put(3001,-3511){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}9\special{ps: grestore}}}} \put(5701,-2911){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}1\special{ps: grestore}}}} \put(6001,-2911){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}2\special{ps: grestore}}}} \put(5701,-5311){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}3\special{ps: grestore}}}} \put(6001,-5311){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}4\special{ps: grestore}}}} \put(6301,-5311){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}5\special{ps: grestore}}}} \put(5701,-4711){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}6\special{ps: grestore}}}} \put(6001,-4711){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}7\special{ps: grestore}}}} \put(5701,-4111){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}9\special{ps: grestore}}}} \put(6301,-4711){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}8\special{ps: grestore}}}} \put(9001,-3061){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_0$\special{ps: grestore}}}} \put(9001,-3661){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_1$\special{ps: grestore}}}} \put(9001,-4261){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_2$\special{ps: grestore}}}} \put(10801,-3061){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_0$\special{ps: grestore}}}} \put(10801,-3661){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_1$\special{ps: grestore}}}} \put(10801,-4261){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_2$\special{ps: grestore}}}} \put(10801,-4861){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_3$\special{ps: grestore}}}} \put(10801,-5461){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_4$\special{ps: grestore}}}} \put(9601,-3511){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-2\special{ps: grestore}}}} \put(9601,-4111){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(10201,-2911){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(10201,-3511){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(10201,-4111){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(10201,-4711){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(10201,-5311){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(9601,-2911){\makebox(0,0)[rb]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(3901,-2911){\makebox(0,0)[b]{\smash{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}5\special{ps: grestore}}}} \end{picture} \end{center} \caption{A balancer} \label{figure:balancer} \end{figure} In the left part, tokens and antitokens are denoted with full and empty circles, respectively; the numbering in the tokens and antitokens reflects the real-time order of tokens and antitokens in an execution where they traverse the balancer sequentially, that is, one completely after the other. For each input index $i$, $0 \leq i < \fin$, we denote by $x_{i}$ the {\em balancer input state variable} that stands for the algebraic sum of the number of tokens and antitokens that have entered on input wire $i$; that is, $x_{i}$ is the number of tokens that have entered {\em minus} the number of antitokens that have entered. Denote $\ax{} = \langle x_{0}, x_{1}, \ldots, x_{\fin-1} \rangle^{{\rm T}}$; call $\ax{}$ an {\em input vector}. For each output index $j$, $0 \leq j < \fout$, we denote by $y_{j}$ the {\em balancer output state variable} that stands for the algebraic sum of the numbers of tokens and antitokens that have exited on output wire $j$; that is, $y_{j}$ is the number of tokens that have exited on output wire $j$ {\em minus} the number of antitokens that have exited on output wire $j$. The right part of Figure~\ref{figure:balancer} shows the corresponding input and output state variables. Denote by $\ay{} = \langle y_{0}, y_{1}, \ldots, y_{\fout-1} \rangle^{{\rm T}}$ the corresponding {\em output vector}. The {\em configuration} of a balancer at any given time is the tuple $\langle \ax{}, \ay{} \rangle$; roughly speaking, the configuration is the collection of its input and output state variables. In the {\em initial configuration,} all input and output wires are empty; hence, in the initial configuration, $\ax{} = \azeroin$, and $\ay{} = \azeroout$. A configuration of a balancer is {\em quiescent} if there are no tokens or antitokens in the balancer. Note that the initial configuration is a quiescent one. The following formal properties are required for an $(\fin, \fout)$-balancer. \begin{enumerate} \item {\em Safety property:} in any configuration, a balancer never creates either tokens or antitokens spontaneously. \item {\em Liveness property:} for any finite number $t$ of tokens and $a$ of antitokens that enter the balancer, the balancer reaches within a finite amount of time a quiescent configuration where $t-e$ tokens and $a-e$ antitokens have exited the network, where $e$, $0 \leq e \leq \min\{t,a\}$, is the number of tokens and antitokens that are ``eliminated'' in the balancer. \item {\em Step property:} in any quiescent configuration, for any pair of output indices $j$ and $k$ such that $0 \leq j < k < \fout$, $0 \leq y_{j} - y_{k} \leq 1$. \end{enumerate} From the safety and liveness properties it follows, for any quiescent configuration $\langle \ax{}, \ay{} \rangle$ of a balancer, that $\| \ax{} \|_1 = \| \ay{} \|_1$. That is, in any quiescent configuration, the algebraic sum of tokens and antitokens that exited the balancer is equal to the algebraic sum of tokens and antitokens that entered it. The equality of sums holds also for the case where some of the tokens and antitokens are ``eliminated'' in the balancer. We are interested in quiescent configurations of a balancer. For any input vector $\ax{}$, denote $\ay{} = b(\ax{})$, the output vector in the quiescent configuration that $b$ will reach after all $\| \ax{} \|_{1}$ tokens and antitokens that entered $b$ have exited; write also $b: \ax{} \to \ay{}$ to denote the balancer $b$. From the step property, for each $0 \leq i < \fout$, each entry $y_i$ of the output vector $\ay{}$ can be written~\cite{AA92,AHS91,BM98} as \begin{eqnarray*} y_i & = & \left\lceil \frac{ \| \ax{} \|_1 - i} {\fout}\, \right\rceil\, . \end{eqnarray*} For any quiescent configuration $\langle \ax{}, \ay{} \rangle$ of a balancer $b: \ax{} \to \ay{}$, the {\em state} of the balancer $b$, denoted $\state_{b}(\langle \ax{}, \ay{} \rangle)$ is defined to be \begin{eqnarray*} \state_{b}(\langle \ax{}, \ay{} \rangle) & = & \| \ax{} \|_1 \mod \fout\, ; \end{eqnarray*} since the configuration is quiescent, it follows that \begin{eqnarray*} \state_{b}(\langle \ax{}, \ay{} \rangle) & = & \| \ay{} \|_1 \mod \fout\, . \end{eqnarray*} For the sake of simplicity we will denote \begin{eqnarray*} \state_{b}(\ax{}) & = & \state_{b}(\langle \ax{}, \ay{} \rangle)\, . \end{eqnarray*} We remark that the state of an $(\fin, \fout)$-balancer is an integer in the set $\{ 0, 1, \ldots, \fout -1 \}$, which captures the ``position'' to which it is set as a toggle mechanism. This integer is determined by either the balancer input state variables or the balancer output state variables in the quiescent configuration. We call the state of the balancer in the initial configuration the {\em initial state}. Note that the initial state of the balancer is $0$. \subsection{Balancing Networks} \label{balancing networks} A {\em $(\win, \wout)$-balancing network} ${\cal B}$ is a collection of interwired balancers, where output wires are connected to input wires, having $\win$ designated input wires, numbered $0, 1, \ldots, \win-1$, which are not connected to output wires of balancers, having $\wout$ designated output wires, numbered $0, 1, \ldots, \wout-1$, similarly not connected to input wires of balancers, and containing no cycles. Tokens and antitokens arrive on the network's input wires at arbitrary times. They traverse a sequence of balancers in the network in a completely asynchronous way and exit on the output wires of the network. \begin{figure}[tp] \begin{center} %\input{8x12.latex} \setlength{\unitlength}{1973sp}% % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \begin{picture}(12170,7045)(1931,-8246) \thinlines \put(4201,-1561){\circle*{140}} \put(4201,-2761){\circle*{140}} \put(5401,-1561){\circle*{140}} \put(5401,-6361){\circle*{140}} \put(6601,-2761){\circle*{140}} \put(5401,-3961){\circle*{140}} \put(6601,-7561){\circle*{140}} \put(6601,-5161){\circle*{140}} \put(4201,-3961){\circle*{140}} \put(4201,-5161){\circle*{140}} \put(7801,-1561){\circle*{140}} \put(7801,-7561){\circle*{140}} \put(9001,-2761){\circle*{140}} \put(9001,-3961){\circle*{140}} \put(9001,-5161){\circle*{140}} \put(9001,-6361){\circle*{140}} \put(4801,-2161){\circle*{140}} \put(4801,-4561){\circle*{140}} \put(4801,-5761){\circle*{140}} \put(4801,-3361){\circle*{140}} \put(6001,-2161){\circle*{140}} \put(6001,-6961){\circle*{140}} \put(7201,-3361){\circle*{140}} \put(7201,-8161){\circle*{140}} \put(8401,-8161){\circle*{140}} \put(8401,-2161){\circle*{140}} \put(6001,-4561){\circle*{140}} \put(7201,-5761){\circle*{140}} \put(9601,-5761){\circle*{140}} \put(9601,-6961){\circle*{140}} \put(9601,-4561){\circle*{140}} \put(9601,-3361){\circle*{140}} \put(10201,-1561){\circle*{140}} \put(10201,-6961){\circle*{140}} \put(10801,-2761){\circle*{140}} \put(10801,-8161){\circle*{140}} \put(11401,-2161){\circle*{140}} \put(11401,-3961){\circle*{140}} \put(11401,-4561){\circle*{140}} \put(11401,-6361){\circle*{140}} \put(12001,-3361){\circle*{140}} \put(12001,-5161){\circle*{140}} \put(12001,-5761){\circle*{140}} \put(12001,-7561){\circle*{140}} \put(12601,-8161){\circle*{140}} \put(12601,-1561){\circle*{140}} \put(13201,-2161){\circle*{140}} \put(13201,-2761){\circle*{140}} \put(13201,-3361){\circle*{140}} \put(13201,-3961){\circle*{140}} \put(13201,-4561){\circle*{140}} \put(13201,-5161){\circle*{140}} \put(13201,-5761){\circle*{140}} \put(13201,-6361){\circle*{140}} \put(13201,-6961){\circle*{140}} \put(13201,-7561){\circle*{140}} \put(3601,-1561){\circle*{140}} \put(3601,-2161){\circle*{140}} \put(3601,-2761){\circle*{140}} \put(3601,-3361){\circle*{140}} \put(3601,-3961){\circle*{140}} \put(3601,-4561){\circle*{140}} \put(3601,-5161){\circle*{140}} \put(3601,-5761){\circle*{140}} \special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-3961){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-5161){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(5401,-6361){\line( 1, 0){8400}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-2761){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-1561){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(6601,-7561){\line( 1, 0){7200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-2161){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-3361){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-4561){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3001,-5761){\line( 1, 0){10800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(6001,-6961){\line( 1, 0){7800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(7201,-8161){\line( 1, 0){6600}} \special{ps: grestore}\thicklines \special{ps: gsave 0 0 0 setrgbcolor}\put(3601,-1561){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3601,-2761){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3601,-3961){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(3601,-5161){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4201,-1561){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4201,-3961){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4801,-2161){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(4801,-4561){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(5401,-1561){\line( 0,-1){4800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(6001,-2161){\line( 0,-1){4800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(6601,-2761){\line( 0,-1){4800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(7201,-3361){\line( 0,-1){4800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(7801,-1561){\line( 0,-1){3000}} \put(7801,-4561){\line( 0,-1){3000}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(8401,-2161){\line( 0,-1){3000}} \put(8401,-5161){\line( 0,-1){3000}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9001,-2761){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9001,-5161){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9601,-3361){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(9601,-5761){\line( 0,-1){1200}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(10201,-1561){\line( 0,-1){5400}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(10801,-2761){\line( 0,-1){5400}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(11401,-2161){\line( 0,-1){1800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(11401,-4561){\line( 0,-1){1800}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(12001,-3361){\line( 0,-1){300}} \put(12001,-3661){\line( 0,-1){300}} \put(12001,-3961){\line( 0,-1){300}} \put(12001,-4261){\line( 0,-1){300}} \put(12001,-4561){\line( 0,-1){300}} \put(12001,-4861){\line( 0,-1){300}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(12001,-5761){\line( 0,-1){300}} \put(12001,-6061){\line( 0,-1){300}} \put(12001,-6361){\line( 0,-1){300}} \put(12001,-6661){\line( 0,-1){300}} \put(12001,-6961){\line( 0,-1){300}} \put(12001,-7261){\line( 0,-1){300}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(12601,-1561){\line( 0,-1){300}} \put(12601,-1861){\line( 0,-1){600}} \put(12601,-2461){\line( 0,-1){300}} \put(12601,-2761){\line( 0,-1){300}} \put(12601,-3061){\line( 0,-1){600}} \put(12601,-3661){\line( 0,-1){300}} \put(12601,-3961){\line( 0,-1){600}} \put(12601,-4561){\line( 0,-1){300}} \put(12601,-4861){\line( 0,-1){300}} \put(12601,-5161){\line( 0,-1){600}} \put(12601,-5761){\line( 0,-1){300}} \put(12601,-6061){\line( 0,-1){300}} \put(12601,-6361){\line( 0,-1){300}} \put(12601,-6661){\line( 0,-1){300}} \put(12601,-6961){\line( 0,-1){300}} \put(12601,-7261){\line( 0,-1){300}} \put(12601,-7561){\line( 0,-1){300}} \put(12601,-7861){\line( 0,-1){300}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(13201,-2161){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(13201,-3361){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(13201,-4561){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(13201,-5761){\line( 0,-1){600}} \special{ps: grestore}\special{ps: gsave 0 0 0 setrgbcolor}\put(13201,-6961){\line( 0,-1){600}} \special{ps: grestore}\put(13501,-1411){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-2011){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-2611){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-3211){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-4411){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-5011){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(13501,-5611){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(13501,-6211){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(13501,-6811){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(13501,-7411){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(13501,-8011){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(3301,-3211){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-11\special{ps: grestore}}}} \put(3301,-2611){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}5\special{ps: grestore}}}} \put(3301,-2011){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}3\special{ps: grestore}}}} \put(3301,-3811){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}8\special{ps: grestore}}}} \put(3301,-4411){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}15\special{ps: grestore}}}} \put(3301,-5011){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-8\special{ps: grestore}}}} \put(3301,-5611){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-7\special{ps: grestore}}}} \put(3901,-1411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(3901,-2011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-4\special{ps: grestore}}}} \put(3901,-2611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(3901,-3211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(3901,-3811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}12\special{ps: grestore}}}} \put(3901,-4411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}11\special{ps: grestore}}}} \put(3901,-5011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-7\special{ps: grestore}}}} \put(3901,-5611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-8\special{ps: grestore}}}} \put(4501,-1411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(4501,-2611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(5101,-2011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-3\special{ps: grestore}}}} \put(5101,-3211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-4\special{ps: grestore}}}} \put(4501,-3811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}3\special{ps: grestore}}}} \put(4501,-5011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}2\special{ps: grestore}}}} \put(5101,-4411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}2\special{ps: grestore}}}} \put(5101,-5611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}1\special{ps: grestore}}}} \put(5701,-1411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(5701,-3811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(5701,-6211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(6301,-2011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(6301,-4411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(6301,-6811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(7501,-3211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(6901,-2611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(6901,-5011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(6901,-7411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(7501,-5611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(7501,-8011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(8101,-1411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(8101,-7411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(8701,-2011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(8701,-8011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(9301,-2611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(9301,-3811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(9301,-5011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(9301,-6211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(9901,-3211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(9901,-4411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(9901,-5611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(9901,-6811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(11101,-2611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(11101,-8011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(11701,-2011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(11701,-3811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(11701,-4411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(11701,-6211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(12301,-3211){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(12301,-5011){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(12301,-5611){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(12301,-7411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(2701,-2161){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_1$\special{ps: grestore}}}} \put(2701,-2761){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_2$\special{ps: grestore}}}} \put(2701,-3361){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_3$\special{ps: grestore}}}} \put(2701,-3961){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_4$\special{ps: grestore}}}} \put(2701,-4561){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_5$\special{ps: grestore}}}} \put(2701,-5161){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_6$\special{ps: grestore}}}} \put(2701,-5761){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_7$\special{ps: grestore}}}} \put(14101,-1561){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_0$\special{ps: grestore}}}} \put(14101,-2161){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_1$\special{ps: grestore}}}} \put(14101,-2761){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_2$\special{ps: grestore}}}} \put(14101,-3361){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_3$\special{ps: grestore}}}} \put(14101,-3961){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_4$\special{ps: grestore}}}} \put(14101,-4561){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_5$\special{ps: grestore}}}} \put(14101,-5161){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_6$\special{ps: grestore}}}} \put(14101,-5761){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_7$\special{ps: grestore}}}} \put(14101,-6361){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_8$\special{ps: grestore}}}} \put(14101,-6961){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_9$\special{ps: grestore}}}} \put(14101,-7561){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_{10}$\special{ps: grestore}}}} \put(14101,-8161){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y_{11}$\special{ps: grestore}}}} \put(10501,-1411){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}0\special{ps: grestore}}}} \put(10501,-6811){\makebox(0,0)[b]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-1\special{ps: grestore}}}} \put(3301,-1411){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}-10\special{ps: grestore}}}} \put(2701,-1561){\makebox(0,0)[rb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x_0$\special{ps: grestore}}}} \end{picture} \end{center} \caption{A balancing network} \label{figure:counting} \end{figure} Figure~\ref{figure:counting} depicts a balancing network with eight input wires and twelve output wires, using the same conventions as in Figure~\ref{figure:balancer}. For each input index $i$, $0 \leq i < \win$, we denote by $x_{i}$ the {\em network input state variable} that stands for the algebraic sum of the numbers of tokens and antitokens that have entered on input wire $i$; that is, $x_{i}$ is the difference between the number of tokens and antitokens that have entered on input wire $i$. Denote $\bx{} = \langle x_{0}, x_{1}, \ldots, x_{\win-1} \rangle^{{\rm T}}$; call $\bx{}$ an {\em input vector}. For each output index $j$, $0 \leq j < \wout$, we denote by $y_{j}$ the {\em network output state variable} that stands for the algebraic sum of the numbers of tokens and antitokens that have exited on output wire $j$; that is, $y_{j}$ is the number of tokens that have exited on output wire $j$ {\em minus} the number of antitokens that have exited on output wire $i$. Denote $\by{} = \langle y_{0}, y_{1}, \ldots, y_{\win-1} \rangle^{{\rm T}}$; call $\by{}$ an {\em output vector}. The {\em configuration} of a network at any given time is the tuple of configurations of its individual balancers. In the {\em initial configuration,} all input and output wires of balancers are empty (hence, all entries in the respective input and output vectors are 0). The safety and liveness properties for a balancing network follow naturally from those of its balancers. Thus, a balancing network eventually reaches a {\em quiescent configuration} in which all tokens and antitokens that entered the network have exited. In any quiescent configuration of $\B$ we have $\| \bx{} \|_{1} = \| \by{} \|_{1}$; that is, in a quiescent configuration, the algebraic sum of tokens and antitokens that exited the network is equal to the algebraic sum of tokens and antitokens that entered it. Naturally, we are interested in quiescent configurations of a network. For any quiescent configuration of a network $\B$ with corresponding input and output vectors $\bx{}$ and $\by{}$, respectively, the {\em state} of $\B$, denoted $\state_{\B}(\bx{})$, is defined to be the collection of the states of its individual balancers. We remark that we have specified $\bx{}$ as the single argument of $\state_{\B}$, since $\bx{}$ uniquely determines all input and output vectors of balancers of $\B$, which are used for defining the states of the individual balancers. As for balancers, we call the state of the balancing network in the initial configuration the {\em initial state}. Note that the initial state of the network is a collection of $0$s. For any input vector $\bx{}$, denote by $\by{} = \B(\bx{})$ the output vector in the quiescent configuration that $\B$ will reach after all $\| \bx{} \|_{1}$ tokens and antitokens that entered $\B$ have exited; write also $\B: \bx{} \to \by{}$ to denote the network $\B$. Not all balancing networks satisfy the step property. A {\em $(\win, \wout)$-counting network} is a {$(\win, \wout)$-balancing network for which, in any quiescent configuration, for any pair of indices $j$ and $k$ such that $0 \leq j < k < \wout$, $0 \leq y_{j} - y_{k} \leq 1$. In other words, the output of a counting network has the step property. For example, the network depicted in Figure~\ref{figure:counting} is a counting network~\cite{BM98}, where the integers on the wires represent the input and output state variables of the balancers that correspond to some particular input vector. The definition of a counting network can be weakened as follows~\cite{AA92,AHS91}. For any integer $K \geq 1$, a {\em $(\win, \wout)$-$K$-smoothing network} is a {$(\win, \wout)$-balancing network for which, in any quiescent configuration, for any pair of indices $j$ and $k$ such that $0 \leq j, k < \wout$, $0 \leq |y_{j} - y_{k}| \leq K$; that is, the output vector of a $K$-smoothing network has the {\em $K$-smoothing property}: all outputs are within $K$ of each other. For a balancing network ${\cal B}$, the {\em depth} of ${\cal B}$, denoted $\depth({\cal B})$, is defined to be the maximum distance from any of its input wires to any of its output wires. In case $\depth({\cal B}) = 1$, ${\cal B}$ will be called a {\em layer}. If $\depth({\cal B}) = d$ is greater than one, then ${\cal B}$ can be uniquely partitioned into layers ${\cal B}_{1}, {\cal B}_{2}, \ldots, {\cal B}_{d}$ from left to right in the obvious way. \subsection{Boundedness Properties} \label{boundedness properties} Fix any integer $g \geq 2$. For any integer $K \geq 1$, the {\em $K$-smoothing property}~\cite{AA92} is defined to be the set of all vectors ${\bf y}^{(g)}$ such that for any entries $y_{j}$ and $y_{k}$ of ${\bf y}^{(g)}$, where $0 \leq j, k < g$, $|y_{j} - y_{k}| \leq K$. A {\em boundedness property} is any subset of some $K$-smoothing property, for any integer $K \geq 1$, that is closed under addition with a constant vector. Clearly, the $K$-smoothing property is trivially a boundedness property; moreover, the set of all vectors ${\bf y}^{(g)}$ that have the {\em step property}~\cite{AHS91} is a boundedness property, since any step vector is 1-smooth (but not vice versa). We remark that there are infinitely many boundedness properties. A boundedness property captures precisely the two properties possessed by both $K$-smooth and step vectors upon which our later proofs will rely. Although we are unaware of any interesting property, other than the $K$-smoothing and step, that is a boundedness one, we chose to state our results for any general boundedness property in order to make explicit the two critical properties that are common to the classes of $K$-smooth vectors and step vectors; moreover, arguing in terms of a boundedness property will allow for a single proof of all claims found to hold for both the $K$-smoothing property and the step property. Say that {\em a vector ${\bf y}$ has the boundedness property ${\bf \Pi}$} if ${\bf y} \in {\bf \Pi}$. Say that {\em a balancing network $\B: \bx{} \to \by{}$ has the boundedness property ${\bf \Pi}$} if for every input vector $\bx{}$, $\B(\bx{}) \in {\bf \Pi}$. %===================================== %===================================== \section{A Simple Proof for Regular Networks} \label{remarks} In this section, we present a simple proof of our main result for a special class of balancing networks that we call ``regular'' balancing networks, and then we explain why this simple proof cannot be applied for the more general class of balancing networks. In a regular balancing network, the input and output width of the network is the same (namely, $\win = \wout$), and the network consists from balancers with equal fan-in and fan-out (namely, $\fin = \fout$ to each balancer). Regular networks appear in \cite{AA92,AHS91,BH99,FLL93}. We continue by proving the main result for regular networks. In particular, we will show that if a regular balancing network satisfies a boundedness property for tokens only (for non-negative input vectors) then it will still satisfy the same boundedness property with both tokens and antitokens (for arbitrary input vectors). For the proof we need the following properties of regular networks which hold for constant input vectors. \begin{lemma} \label{regular-constant} Consider a regular balancing network $\B: \bxw{} \to \byw{}$. Let $\bzw{}$ be any constant input vector. Then, \begin{eqnarray} \B(\bzw{}) & = & \bzw{}\,. \end{eqnarray} \end{lemma} \begin{proof} Since vector $\bzw{}$ is constant, there is a constant $c$ such that $z_i = c$, for all $0 \leq i < w$. First, consider the case where $\B$ is a single balancer $b$. Since the output of balancer $b$ satisfies the step property, we have for each index $i$, where $0 \leq i