\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 <w$,
\begin{eqnarray*}
(\B(\bzw{}))_i & = & (b(\bzw{}))_i \\
& = & \left \lceil \frac { \|\bzw{}\|_1 - i} { w} \right \rceil \\
& = & \left \lceil \frac { c \cdot w - i} {w} \right \rceil \\
& = & \left \lceil c - \frac { i} {w} \right \rceil \\
& = & c + \left \lceil - \frac { i} {w} \right \rceil \\
& = & c \, , 
\end{eqnarray*}
and thus, $\B(\bzw{}) = \bzw{}$.

Now, consider the case where the network $\B$ consists from more
than one balancer.
We will prove the claim by induction on the depth $d$ of the network.
For the basis case where $d=1$, 
$\B$ is just a single layer of balancers, 
and the claim follows immediately by applying 
the single balancer case
to each of the balancers in the layer.

Let's assume inductively that 
the claim holds 
for all networks of
depth at most $d-1$.
For the induction step,
let $\B = \B' \B''$, 
where $\B'$ and $\B''$ are regular networks
of input/output widths $w$ 
and depth at most $d-1$;
that is,
$\B$ is the ``cascade''
of $\B'$ and $\B''$.
Obviously,
for any input vector $\bxw{}$,
$\B(\bxw{}) = \B''(\B'(\bxw{}))$.

We continue with the induction step.
We have,
$\B(\bzw{}) = \B''(\B'(\bzw{}))$.
From the induction hypothesis for network $\B'$,
we have $\B'(\bzw{}) = \bzw{}$.
Subsequently, $\B''(\B'(\bzw{})) = \B''(\bzw{})$.
From the induction hypothesis for $\B''$ we have,
$\B''(\bzw{}) = \bzw{}$.
Subsequently,
$\B(\bzw{}) = \bzw{}$, as needed.
\end{proof}


\begin{lemma}
\label{regular-linearity}
Consider a regular balancing network 
$\B: \bxw{} 
     \to 
     \byw{}$.
Let $\bzw{}$ be any constant input vector,
and $\bxw{}$ be an arbitrary input vector.
Then,
\begin{eqnarray}
\B(\bzw{} + \bxw{}) & = & \B(\bzw{}) + \B(\bxw{})\,.
\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 only a single balancer $b$.
Since the output of balancer $b$ 
satisfies the step property, 
we have
for each index $i$, where $0 \leq i <w$,
\begin{eqnarray*}
(\B(\bzw{} + \bxw{}))_i & = & (b(\bzw{} + \bxw{}))_i \\
& = & \left \lceil \frac { \|\bzw{} + \bxw{}\|_1 - i} {w} \right \rceil \\
& = & \left \lceil \frac { \|\bzw{}\|_1 + \|\bxw{}\|_1 - i} {w} \right \rceil \\
& = & \left \lceil \frac { c \cdot w + \|\bxw{}\|_1 - i} {w} \right \rceil \\
& = & \left \lceil c + \frac {\|\bxw{}\|_1 - i} {w} \right \rceil \\
& = & c + \left \lceil\frac {\|\bxw{}\|_1 - i} {w} \right \rceil \\
& = & c + (b(\bxw{}))_i \\
& = & z_i + (\B(\bxw{}))_i \\
& = & (\B(\bzw{}))_i + (\B(\bxw{}))_i\,, \\
&   & \mbox{(by Lemma \ref{regular-constant})}
\end{eqnarray*}
and thus, 
$\B(\bzw{} + \bxw{}) = \B(\bzw{}) + \B(\bxw{})$.

Now, consider the case where the network $\B$ consists from more
than one balancer.
We will prove the claim by induction on the depth $d$ of the network.
For the basis case where $d=1$, 
$\B$ is just a single layer of balancers, 
and the claim follows immediately by applying 
the single balancer case
to each of the balancers in the layer.

Let's assume inductively that 
the claim holds 
for all networks of
depth at most $d-1$.
For the induction step,
let $\B = \B' \B''$, 
where $\B'$ and $\B''$ are regular networks
of input/output widths $w$ 
and depth at most $d-1$;
that is,
$\B$ is the ``cascade''
of $\B'$ and $\B''$.

We continue with the induction step.
We have,
\begin{eqnarray*}
\B(\bzw{} + \bxw{}) & = & \B''(\B'(\bzw{} + \bxw{}))\,.
\end{eqnarray*}
From the induction hypothesis for network $\B'$,
we have,
\begin{eqnarray*}
\B'(\bzw{} + \bxw{}) & = & \B'(\bzw{}) + \B'(\bxw{})\,,
\end{eqnarray*}
and by Lemma \ref{regular-constant},
we obtain
\begin{eqnarray*}
\B'(\bzw{} + \bxw{}) & = & \bzw{} + \B'(\bxw{})\,.
\end{eqnarray*}
Subsequently, 
\begin{eqnarray*}
\B''(\B'(\bzw{} + \bxw{})) 
& = & \B''(\bzw{} + \B'(\bxw{})) \\
& = & \B''(\bzw{}) + \B''(\B'(\bxw{})) \\
&   & \mbox{(by the induction hypothesis for $\B''$)} \\
& = & \bzw{} + \B(\bxw{}) \\
& = & \B(\bzw{}) + \B(\bxw{})\,, \\
&   & \mbox{(by applying Lemma \ref{regular-constant} twice)} \\      
\end{eqnarray*}
and it follows that 
$\B(\bzw{} + \bxw{}) = \B(\bzw{}) + \B(\bxw{})$, as needed. 
\end{proof}

We are now ready to show the main result for regular networks.

\begin{theorem}
\label{regular-main}
Fix any boundedness property
${\bf \Pi}$.
Consider any regular balancing network
$\B : \bxw{}
      \to
      \byw{}$
such that the output vector $\byw{}$
has the boundedness property ${\bf \Pi}$
whenever the input vector
$\bxw{}$
is non-negative.
Then,
$\B$ has the boundedness property ${\bf \Pi}$.
\end{theorem}

\begin{proof}
Assume that $\B$ has the boundedness property ${\bf \Pi}$
for non-negative input vectors.
Let $\bxw{}$ be an arbitrary input vector 
(which may contain negative entries).
We will show that $\B(\bxw{}) \in {\bf \Pi}$.

Construct from vector $\bxw{}$, 
a constant vector $\bzw{}$ so that the vector
$\bzw{} + \bxw{}$ is non-negative
($\bzw{}$ could simply consist from the absolute value
of the smallest entry of $\bxw{}$).
By Lemma \ref{regular-linearity}, 
we have 
\begin{eqnarray*}
\B(\bxw{}) & = & \B(\bzw{} + \bxw{}) - \B(\bzw{})\,.
\end{eqnarray*}
Subsequently, by Lemma \ref{regular-constant},
we obtain
\begin{eqnarray*}
\B(\bxw{}) & = & \B(\bzw{} + \bxw{}) - \bzw{}\,.
\end{eqnarray*}  
Since the vector $\bzw{} + \bxw{}$ is non-negative,
we have from hypothesis that 
$$\B(\bzw{} + \bxw{}) \in {\bf \Pi}\,.$$
Furthermore, since ${\bf \Pi}$ is a boundedness property, 
${\bf \Pi}$ is closed
under the addition with a constant vector,
and since $\bzw{}$ is a constant vector,
it follows that 
$$\B(\bzw{} + \bxw{}) + \bzw{} \in {\bf \Pi}\,.$$
Therefore, $\B(\bxw{}) \in {\bf \Pi}$, as needed.
\end{proof}

We want to note here that the proof of Theorem \ref{regular-main},
holds only for regular balancing networks. 
The reason for this is 
that Lemmas \ref{regular-constant}
and \ref{regular-linearity},
hold only for regular balancing networks.
These lemmas do not apply for the general case of balancing networks,
in which the input width may differ from the output width
(namely, $\win \neq \wout$).

For instance, consider the simple non-regular network $\B$ which 
consists from only one $(2,3)$-balancer.
Take the constant input vector 
$\langle 1, 1\rangle^{{\rm T}}$.
The respective output vector is 
$\langle 1, 1,0\rangle^{{\rm T}}$,
which is non-constant.
Subsequently, Lemma \ref{regular-constant} does not
hold for the specific network $\B$. 

Therefore, we need to take a different approach
for general balancing networks.
In Sections \ref{fooling pairs}, and ~\ref{null vectors},
we will identify the class of input vectors for which
properties like the ones in
Lemmas \ref{regular-constant}
and \ref{regular-linearity} hold
for general balancing networks.
Using these new kinds of vectors,
we prove in section~\ref{equivalence result},
our main result for general networks.

%=====================================
%=====================================

\section{Fooling Pairs}
\label{fooling pairs}

In this section, we introduce fooling pairs and prove several of their
properties.


Say that input vectors $\ax{1}$ and $\ax{2}$ are a {\em fooling pair
to balancer $b: \ax{} \to \ay{}$} if
\begin{eqnarray*}
      \state_{b}(\ax{1})
& = & \state_{b}(\ax{2})\, ;
\end{eqnarray*}
roughly speaking, a fooling pair transitions the balancer to identical
states in the two corresponding quiescent configurations.  We start by
showing:

 


\begin{proposition}
\label{balancer fooling pair}
Consider a balancer
$b: \ax{} 
    \to 
    \ay{}$.
Take any input vectors 
$\ax{1}$ and 
$\ax{2}$
that are a fooling pair
to balancer $b$.
Then, 
for any input vector $\ax{}$,
\begin{eqnarray*}
b(\ax{1} + \ax{}) - b(\ax{1}) 
& = & 
b(\ax{2} + \ax{}) - b(\ax{2})\,.
\end{eqnarray*} 
\end{proposition}




\begin{proof}
Since the output of balancer $b$ satisfies the step property,
we have for each entry $i$, where $0 \leq i < \fout$,
of vector $b(\ax{1} + \ax{}) - b(\ax{1})$,
\begin{eqnarray*}
&   &   (b(\ax{1} + \ax{}) - 
        b(\ax{1}))_i                                                             
\\
& = & \left\lceil 
       \frac{\| \ax{1} + \ax{} \|_1 - i} 
              {\fout} 
      \right \rceil -
      \left\lceil 
       \frac{\| \ax{1} \|_1 - i}
              {\fout} 
      \right \rceil                                                           
\\
& = & \left\lceil 
       \frac{\| \ax{1} \|_1 + \| \ax{} \|_1 - i}
              {\fout} 
      \right \rceil -
      \left\lceil 
       \frac{\| \ax{1} \|_1 - i}
            {\fout} 
      \right\rceil                                                            
\\
& = & \left\lceil 
       \frac{(\| \ax{1} \|_1 \divd \fout) \cdot \fout +
             (\| \ax{1} \|_1 \mod \fout) +
             \| \ax{} \|_1 - i} 
            {\fout}
      \right\rceil -                                                          
\\
&   & \left\lceil 
       \frac{(\| \ax{1} \|_1 \divd \fout) \cdot \fout +
             (\| \ax{1} \|_1 \mod \fout) - i} 
            {\fout} 
      \right\rceil                                                            
\\
& = & \left\lceil 
       (\| \ax{1} \|_1 \divd \fout) +
        \frac{ \state_b(\ax{1}) + \| \ax{} \|_1 - i}
             {\fout} 
      \right \rceil -                                                         
\\
&   & \left\lceil 
       (\| \ax{1} \|_1 \divd \fout) +
        \frac{ \state_b(\ax{1}) - i}
               {\fout} 
      \right \rceil                                                           
\\
&   & \mbox{(by definition of $\state_b$)}                                    
\\
& = & (\| \ax{1} \|_1 \divd \fout) +
      \left\lceil 
             \frac{ \state_b(\ax{1}) + \| \ax{} \|_1 - i}
             {\fout} 
      \right \rceil -                                                         
\\
&   & (\| \ax{1} \|_1 \divd \fout) -
       \left\lceil 
               \frac{ \state_b(\ax{1}) - i}
               {\fout} 
      \right \rceil                                                           
\\
& = & \left\lceil 
             \frac{ \state_b(\ax{1}) + \| \ax{} \|_1 - i}
             {\fout} 
      \right \rceil -                                                         
       \left\lceil 
               \frac{ \state_b(\ax{1}) - i}
               {\fout} 
      \right \rceil\,.
\end{eqnarray*}
Similarly,
we can show that
\begin{eqnarray*}
&   & (b(\ax{2} + \ax{}) - b(\ax{2}))_i \\
& = & \left\lceil 
       \frac{\state_b(\ax{2}) + \| \ax{} \|_1 - i}
            {\fout} 
      \right \rceil -
      \left\lceil 
       \frac{\state_b(\ax{2})\ - i} 
            {\fout}
      \right\rceil\, .
\end{eqnarray*}
Since $\ax{1}$ and $\ax{2}$ 
are a fooling pair to $b$,
$\state_b(\ax{1}) 
 = 
 \state_b(\ax{2})$.
It follows that
\begin{eqnarray*}
      b(\ax{1} + \ax{}) - b(\ax{1}) 
& = & b(\ax{2} + \ax{}) - b(\ax{2})\, ,
\end{eqnarray*}
as needed.
\end{proof}




We continue to extend the concept of a fooling pair from a single
balancer to a network.  Say that input vectors $\bx{1}$ and $\bx{2}$
are {\em a fooling pair to network $\B: \bx{} \to \by{}$} if for each
balancer $b$ of $\B$, the input vectors of $b$ in quiescent
configurations corresponding to $\bx{1}$ and $\bx{2}$, respectively,
are a fooling pair to $b$; roughly speaking, a fooling pair
transitions all balancers of the network to identical states in the
two corresponding quiescent configurations.  We continue to generalize
Proposition~\ref{balancer fooling pair} to the case of a balancing
network.




\begin{proposition}
\label{balancing fooling pair}
Consider a balancing network
$\B: \bx{} 
     \to 
     \by{}$.
Take any input vectors 
$\bx{1}$ and $\bx{2}$
that are a fooling pair to network $\B$.
Then, 
for any input vector $\bx{}$,
\begin{eqnarray*}
\B(\bx{1} + \bx{}) - \B(\bx{1}) 
& = &
\B(\bx{2} + \bx{}) - \B(\bx{2})\,. 
\end{eqnarray*}
\end{proposition}




\begin{proof}
By induction on 
the depth $d$ 
of the network $\B$.
For the basis case, 
where $d=1$, 
$\B$ is a single layer, 
and the claim follows immediately
by applying Proposition~\ref{balancer fooling pair}
to each of the balancers of $B$
separately.

Let's assume inductively that 
the claim holds 
for all networks of
depth at most $d-1$.
For the induction step,
let $\B = \B' \B''$, 
where $\B': \bx{} 
            \to 
            \bz{}$
and $\B'': \bz{} 
           \to 
           \by{}$
are networks 
of depth at most $d-1$;
that is,
$\B$ is the ``cascade''
of $\B'$ and $\B''$.
Obviously, for any input vector $\bx{}$,
$\B(\bx{}) = \B''(\B'(\bx{}))$. 


We continue with the induction step.
Since the input vectors $\bx{1}$ and $\bx{2}$ 
are a fooling pair to $\B$,
it follows that 
they are a fooling pair to $\B'$.
So, 
by induction hypothesis for $\B'$,
\begin{eqnarray*}
      \B'(\bx{1} + \bx{}) 
& = & \B'(\bx{1}) + 
      \B'(\bx{2} + \bx{}) - \B'(\bx{2})\, .
\end{eqnarray*}  
Thus,
\begin{eqnarray*}
&   & \B(\bx{1} + \bx{}) - 
      \B(\bx{1})                                                               
\\
& = & \B''(\B'(\bx{1} + \bx{})) - 
      \B''(\B'(\bx{1}))                                                        
\\
& = & \B''(\B'(\bx{1}) + \B'(\bx{2} + \bx{}) - \B'(\bx{2})) -
      \B''(\B'(\bx{1}))\, .
\end{eqnarray*}

Since the input vectors $\bx{1}$ and $\bx{2}$ 
are a fooling pair to $\B$,
it follows that the vectors 
$\B'(\bx{1})$ and $\B'(\bx{2})$
are a fooling pair to $\B''$.
Thus, 
we apply induction hypothesis for $B''$
by taking 
$\B'(\bx{1})$ for $\bx{1}$,
$\B'(\bx{2})$ for $\bx{2}$,
and
$\B'(\bx{2} + \bx{}) - \B'(\bx{2})$
for $\bx{}$,
to obtain that
\begin{eqnarray*}
&   & \B''(\B'(\bx{1}) + 
           \B'(\bx{2} + \bx{}) - 
           \B'(\bx{2})
          )                       -
      \B''(\B'(\bx{1}))                                                        
\\
& = & \B''(\B'(\bx{2}) + 
           \B'(\bx{2} + \bx{}) - 
           \B'(\bx{2}))            -
      \B''(\B'(\bx{2}))                                                        
\\
& = & \B''(\B'(\bx{2} + \bx{})
          )                       -
      \B''(\B'(\bx{2}))                                                        
\\
& = & \B(\bx{2} + \bx{}) - 
      \B(\bx{2})\, .
\end{eqnarray*}
It follows that
$      \B(\bx{1} + \bx{}) - 
      \B(\bx{1})
 =  \B(\bx{2} + \bx{}) - 
      \B(\bx{2})$,
as needed.
\end{proof} 

In Appendix \ref{fooling pairs -- appendix},
we present some additional properties for fooling pairs,
which are of general interest and
give further insight into fooling pairs.

%=========================================
%=========================================
\section{Null Vectors}
\label{null vectors}

Fooling pairs define equivalence classes of input vectors.  If an
input vector transitions the balancing network to a specific state,
then all vectors, which are fooling pairs with this specific input
vector, belong to the same equivalent class.  Each equivalence class
has an associated state, the one to which the input vectors of the
equivalence class transition the network.  An interesting equivalence
class is the set of {\em null vectors}, whose associated state is
identical to the initial state of the network.  

Formally, we say that $\bx{}$ is a {\em null vector} to network $\B:
\bx{} \to \by{}$ if the vectors $\bx{}$ and $\bzeroin$ are a fooling
pair to $\B$.  Intuitively, a null vector ``hides'' itself in the
sense that it does not alter the initial state of $\B$, by traversing
it.  We obtain the following linearity result for null vectors.

\begin{proposition}
\label{null vector linearity} 
Consider a balancing network
$\B: \bx{} 
     \to 
     \by{}$.
Take any null input vector 
$\bx{1}$ to network $\B$.
Then, 
for any input vector $\bx{}$,
\begin{eqnarray*}
\B(\bx{1} + \bx{}) & = & \B(\bx{1}) + \B(\bx{})\,.
\end{eqnarray*}
\end{proposition}

\begin{proof}
From Proposition~\ref{balancing fooling pair},
by taking $\bx{1}$ for $\bx{1}$,
$\bzeroin$ for $\bx{2}$,
and $\bx{}$ for $\bx{}$,
we have,
\begin{eqnarray*}
\B(\bx{1} + \bx{}) - \B(\bx{1})
& = & \B(\bzeroin + \bx{}) - \B(\bzeroin) \\
& = & \B(\bx{}) - \bzeroout \\
&   & \mbox{(since $\B(\bzeroin) = \bzeroout$)}\\
& = & \B(\bx{})\,.
\end{eqnarray*}
Therefore,
$\B(\bx{1} + \bx{}) = \B(\bx{1}) + \B(\bx{})$,
as needed.
\end{proof}

We continue to show:

\begin{proposition}
\label{multiple linearity}
Consider a balancing network 
$\B: \bx{} 
     \to 
     \by{}$.
Take any input vector
$\bx{}$
that is null to $\B$.
Then, 
for any integer $k \geq 0$,
\begin{eqnarray*}
\B(k\bx{}) & = & k \B(\bx{})\, .
\end{eqnarray*}
\end{proposition}




\begin{proof}

We proceed by induction on $k$.
For the basis case 
where $k=0$, 
the claim holds trivially.
Assume inductively that
the claim holds for all integers $k'$ 
such that $k' \leq k-1$.
For the induction step, 
consider the integer $k$.
Clearly,
\begin{eqnarray*}
      k\bx{} 
& = & \bx{} + (k-1) \bx{}\, ,
\end{eqnarray*}
so that
\begin{eqnarray*}
      \B(k\bx{}) 
& = & \B(\bx{} + (k-1)\bx{})\, .
\end{eqnarray*}

We apply Proposition~\ref{null vector linearity}
by taking
$\bx{}$ for $\bx{1}$ and
$(k-1)\bx{}$ for $\bx{}$,
to obtain that
\begin{eqnarray*}
 \B(\bx{} + (k-1)\bx{})
& = & \B(\bx{}) + \B((k-1)\bx{}) \\
& = & \B(\bx{}) + (k-1)\B(\bx{}) \\
&   & \mbox{(by induction hypothesis)}          \\
& = & k \B(\bx{})\, .
\end{eqnarray*}
Therefore, $\B(k\bx{}) = k \B(\bx{})$, as needed.
\end{proof}




For any balancing network $\B$, denote by $\Wout(\B)$ the product of the
fan-outs of balancers of $\B$.  The next claim establishes a
sufficient condition for null vectors.




\begin{proposition}
\label{fanout null vector}
Consider a balancing network 
$\B: \bx{} 
     \to 
     \by{}$.
Assume that 
$\Wout(\B)$ divides $\bx{}$.
Then 
$\bx{}$ is  a null vector
to $\B$.
\end{proposition}




\begin{proof}
By induction on the depth $d$ of $\B$.  For the base case where $d=1$,
$\B$ is a single layer.  Take any single balancer $b: \ax{} \to \ay{}$
of $\B$.  By definition of $\Wout(\B)$, $\fout$ divides $\Wout(\B)$.
Since $\Wout(\B)$ divides $\bx{}$, it follows that $\fout$ divides
$\bx{}$.  Hence, $\fout$ divides the restriction $\ax{}$ of $\bx{}$
so that $\ax{}$ is a null vector to $b$.  Since $b$ was chosen
arbitrarily, this implies that $\bx{}$ is a null vector to $\B$, as
needed.




Assume inductively that 
the claim holds for all balancing networks
of depth at most $d-1$.
Write $\B = \B' \B''$,
where each of $\B'$ and $\B''$ 
is a balancing network 
of depth at most $d-1$.
Since $\Wout(\B)$ divides $\bx{}$ and 
$\Wout(\B) = \Wout(\B') \Wout(\B'')$,
it follows that 
$\Wout(\B')$ divides $\bx{}$.
 By the induction hypothesis for network $\B'$,
it now follows 
that $\bx{}$ is a null vector
to network $\B'$.




It remains to be shown that $\B'(\bx{})$ is a null vector to network
$\B''$.  Since $\Wout(\B'')$ divides $\bx{}$,
Proposition~\ref{multiple linearity} for $\B'$ (by taking $\Wout(\B'')$
for $k$, and $\bx{} / \Wout(\B'')$ for $\bx{}$), implies that
$\Wout(\B'')$ divides $\B'(\bx{})$.  Thus, by induction, the hypothesis for
network $\B''$, $\B'(\bx{})$ is a null vector to network $\B''$, which
completes the proof.
\end{proof}



In Appendix \ref{null vectors -- appendix}, we present some additional
properties for null vectors which are of general interest, and give
further insight into null vectors.


%=====================================
%=====================================

\section{Equivalence}
\label{equivalence result}
In this section,
we show our main equivalence result.
We start by proving:




\begin{proposition}
\label{constant output vector}
Fix any boundedness property
${\bf \Pi}$.
Consider any balancing network
$\B: \bx{}
     \to
     \by{}$
that has the boundedness property ${\bf \Pi}$
whenever the input vector $\bx{}$ is non-negative.
Assume that
$\bx{}$ is a null non-negative input vector.
Then,
the respective output vector $\by{}$ is constant.
\end{proposition}




\begin{proof}
Assume, by way of contradiction, that there exist entries $y_{j}$ and
$y_{k}$ of $\by{}$ such that $y_{j} \neq y_{k}$.  Clearly, $|y_{j} -
y_{k}| \geq 1$.

Since $\B$ has the boundedness property, it follows that $|y_{j} -
y_{k}| \leq K$ for some universal integer $K \geq 1$.




Since $\bx{}$ is a null vector, it follows by
Proposition~\ref{multiple linearity}, that
\begin{eqnarray*}
\B((K+1)\bx{})
& = & (K+1) \B(\bx{}) \\
& = & (K+1) \by{}\, .
\end{eqnarray*}



Since $(K+1)\bx{}$ is a non-negative input vector,
and since $\B$ has the
boundedness property for non-negative input vectors,
we have that the output vector $(K+1)\by{}$
has the boundedness property ${\bf \Pi}$.
Subsequently,
for the $j$th and $k$th entries
$y_{j}^{\prime}$ and 
$y_{k}^{\prime}$,
respectively,
of $(K+1)\by{}$,
we have 
\begin{eqnarray*}
|y_{j}^{\prime} - y_{k}^{\prime}| & \leq & K\, .
\end{eqnarray*} 
However,
\begin{eqnarray*}
      y_{j}^{\prime} - y_{k}^{\prime}
& = & (K+1) y_{j} - (K+1) y_{k}            \\            
& = & (K+1) (y_{j} - y_{k})\, ,
\end{eqnarray*}
so that
\begin{eqnarray*}
      |y_{j}^{\prime} - y_{k}^{\prime}|
& = & (K+1) |y_{j} - y_{k}|                \\
& \geq & K+1\, ,
\end{eqnarray*}
a contradiction.
\end{proof}




We finally show
our main result:




\begin{theorem}
\label{main}
Fix any boundedness property
${\bf \Pi}$.
Consider any balancing network
$\B : \bx{}
      \to
      \by{}$
such that $\by{}$
has the boundedness property ${\bf \Pi}$
whenever the input vector
$\bx{}$
is non-negative.
Then,
$\B$ has the boundedness property ${\bf \Pi}$.
\end{theorem}




\begin{proof}
Consider any arbitrary input vector
$\bx{}$.
We will show that
$\B(\bx{})$
has the boundedness property ${\bf \Pi}$.




Construct from $\bx{}$
an input vector $\tbx{}$
such that
for each index $i$,
$0 \leq i 
   < \win$,
$\tilde{x}_{i}$ is 
the least multiple of $\Wout(\B)$
such that
$\tilde{x}_{i} + x_{i}
 \geq
 0$.
Clearly, both vectors $\tbx{}$ and $\tbx{} + \bx{}$
are non-negative.
Furthermore,
$\Wout(\B)$
divides $\tbx{}$,
and therefore,
by Proposition~\ref{fanout null vector},
we have that $\tbx{}$ is a null vector.
Since $\tbx{}$ is non-negative,
by Proposition~\ref{constant output vector}, 
we have that $\B(\tbx{})$
is a constant vector.
We apply Proposition~\ref{null vector linearity}
with $\tbx{}$ for $\bx{1}$,
and $\bx{}$ for $\bx{}$;
we obtain that
\begin{eqnarray*}
      \B(\tbx{} + \bx{})
& = & \B(\tbx{}) + \B(\bx{})\, ,
\end{eqnarray*}
so that
\begin{eqnarray*}
      \B(\bx{})
& = & \B(\tbx{} + \bx{}) -
      \B(\tbx{})\, .
\end{eqnarray*}




Since $\tbx{} + \bx{}$ is a non-negative input vector, it follows, by
assumption on $\B$, that $\B(\tbx{} + \bx{})$ has the boundedness
property ${\bf \Pi}$.  Since $\B(\tbx{})$ is a constant vector, it
follows, by closure of the boundedness property under addition with a
constant vector, that $\B(\bx{})$ has the boundedness property ${\bf
\Pi}$, as needed.
\end{proof}


%=====================================
%=====================================

\section{Conclusion}
\label{conclusion}

We have shown that any balancing network that satisfies a given
boundedness property on all non-negative input vectors, will also
satisfy the same property for any arbitrary input vector.  Interesting
examples of such properties are the step property and the
$K$-smoothing property.  A significant consequence of our result is
that all known (deterministic) constructions of counting and smoothing
networks~\cite{AA92,AVY94,AHS91,BHM94,BM98,FLL93,HKM93,K94,KP92,SZ96}
will correctly handle both tokens and antitokens, and therefore
simultaneously support both the increment and decrement operations.
Another significant consequence is that the sufficient timing
conditions for linearizability in counting networks established
in~\cite{LSST96,MPT97} immediately carry over when introducing
antitokens in addition to tokens. Our work leaves open several
interesting questions and problems.




Aiello {\em et al.}~\cite{AVY94}
present an interesting construction of
a {\em randomized} counting network;
they use {\em randomized balancers,}
which distribute tokens 
on output wires 
according to some random permutation.
Does this network operate correctly 
when simultaneously traversed
by both tokens and antitokens?
It seems to appear that
the randomized balancers 
need to somehow ``remember''
the entire history of the random permutations
in order for antitokens (resp., tokens)
to trace back the paths of tokens 
(resp., antitokens).




Other interesting properties 
of balancing networks
include the {\em threshold property}~\cite{AHS91,BM97}
and the {\em weak threshold property}~\cite{BM97},
outlined below.
Let $\bx{}$ and $\by{}$
be the input vector 
and the corresponding output vector
of a balancing network 
that has any of these properties.
For the threshold property,
we require that 
$y_0 = \lceil \| \bx{} \|_{1}/ \wout \rceil$,
while for the weak threshold property,
we require that 
there is {\em some} output index $j$,
possibly $j \neq 0$, 
such that 
$y_j = \lceil \| \bx{} \|_{1}/ \wout \rceil$. 
Since we have not established
that either of these properties is a boundedness property,
our result does not apply a fortiori 
to these properties.
It would be extremely interesting 
to see whether 
these properties are preserved
by the introduction of antitokens.
We conjecture that
different techniques are required
for handling these questions.




\newpage



\bibliographystyle{abbrv}
\bibliography{anti}


\newpage

\appendix


%========================================
%========================================
\section{Fooling Pairs}
\label{fooling pairs -- appendix}

We present some additional properties 
of fooling pairs
which complement the properties 
presented in Section \ref{fooling pairs}.
%These new properties are of general interest
%and give further insight for fooling pairs.

We begin by giving a simple linearity result for the state of a
balancer.  From the linearity property of the modulo operation we
immediately obtain the following result:

\begin{lemma}
\label{linearity for balancer}
Consider a balancer
$b: \ax{}
    \to
    \ay{}$.
Then,
for any input vectors
$\ax{1}$ and $\ax{2}$,
\begin{eqnarray*}
      \state_{b}(\ax{1} + \ax{2})
& = & (\state_{b}(\ax{1}) +
       \state_{b}(\ax{2}))
      \mod
      \fout\, .
\end{eqnarray*}
\end{lemma}

Next, we show that in a balancer,
whenever we add a vector to a fooling pair,
the result is still a fooling pair. 
This result is complementary to 
Proposition~\ref{balancer fooling pair}.

\begin{proposition}
\label{balancer fooling pair sum}
Consider a balancer
$b: \ax{} 
    \to 
    \ay{}$.
Take any input vectors 
$\ax{1}$ and 
$\ax{2}$
that are a fooling pair
to balancer $b$.
Then, 
for any input vector $\ax{}$,
the input vectors 
$\ax{1} + \ax{}$ and 
$\ax{2} + \ax{}$
are a fooling pair to balancer $b$.
\end{proposition}
\begin{proof}
Clearly, 
by Lemma~\ref{linearity for balancer}, 
\begin{eqnarray*}
      \state_b(\ax{1} + \ax{})
& = & (\state_b(\ax{1}) + \state_b(\ax{})) \mod \fout\, ,
\end{eqnarray*}
and
\begin{eqnarray*}
      \state_b(\ax{2} + \ax{})
& = & (\state_b(\ax{2}) + \state_b(\ax{}))
      \mod \fout\, .
\end{eqnarray*}
Since $\ax{1}$ and $\ax{2}$ are a fooling pair
to $b$,
$\state_b(\ax{1}) = \state_b(\ax{2})$,
and it follows that
\begin{eqnarray*}
      \state_b(\ax{1} + \ax{}) 
& = & \state_b(\ax{2} + \ax{});
\end{eqnarray*}
thus,
$\ax{1} + \ax{}$ and 
$\ax{2} + \ax{}$
are a fooling pair to $b$,
as needed.
\end{proof}

Next, we generalize
the previous result to balancing networks.
Namely, we show that in a balancing network,
when we add a vector to a fooling pair,
the result is still a fooling pair. 
This result is complementary to 
Proposition~\ref{balancing fooling pair}.

\begin{proposition}
\label{balancing fooling pair sum} 
Consider a balancing network
$\B: \bx{} 
     \to 
     \by{}$.
Take any input vectors 
$\bx{1}$ and $\bx{2}$
that are a fooling pair to network $\B$.
Then, 
for any input vector $\bx{}$,
the input vectors 
$\bx{1} + \bx{}$ and 
$\bx{2} + \bx{}$
are a fooling pair to network $\B$.
\end{proposition}




\begin{proof}
By induction on the depth $d$ of the network $\B$.  For the base case
where $d=1$, $\B$ is a single layer, and the claim follows immediately
by applying Proposition~\ref{balancer fooling pair sum} to each of the
balancers of $B$ separately.




Assume inductively that the claim holds for all networks of depth at
most $d-1$.  For the induction step, let $\B = \B' \B''$, where $\B':
\bx{} \to \bz{}$ and $\B'': \bz{} \to \by{}$ are networks of depth at
most $d-1$; that is, $\B$ is the ``cascade'' of $\B'$ and $\B''$.


We continue with the induction step.
Since the input vectors 
$\bx{1}$ and $\bx{2}$ 
are a fooling pair to $\B$,
it follows that 
they are a fooling pair to $\B'$.
Thus, 
by the induction hypothesis for $\B'$,
for any input vector $\bx{}$, 
the input vectors $\bx{1} + \bx{}$
and $\bx{2} + \bx{}$ 
are a fooling pair to $\B'$.
It remains to be shown that
the vectors
$\B'(\bx{1} + \bx{})$ and
$\B'(\bx{2} + \bx{})$ 
are a fooling pair to $\B''$.

By applying Proposition~\ref{balancing fooling pair}
to $\B'$,
\begin{eqnarray*}
      \B'(\bx{1} + \bx{}) - \B'(\bx{1}) 
& = & \B'(\bx{2} + \bx{}) - \B'(\bx{2})\, ,
\end{eqnarray*}
while, 
by assumption, 
$\B'(\bx{1})$ and $\B'(\bx{2})$
are a fooling pair for $\B''$.
We apply the induction hypothesis to $\B''$,
taking 
$\B'(\bx{1})$ for $\bx{1}$,
$\B'(\bx{2})$ for $\bx{2}$,
and
$\B'(\bx{1} + \bx{}) - \B'(\bx{1})$
for $\bx{}$;
it implies that
the input vectors
\begin{eqnarray*}
&   &  \B'(\bx{1}) + 
      \B'(\bx{1} + \bx{}) - 
      \B'(\bx{1})
\\
& = & \B'(\bx{1} + \bx{})\, ,
\end{eqnarray*}
and
\begin{eqnarray*}
&   &      \B'(\bx{2}) + 
      \B'(\bx{1} + \bx{}) - 
      \B'(\bx{1})
\\
& = &
 \B'(\bx{2}) + 
      \B'(\bx{2} + \bx{}) - 
      \B'(\bx{2})
\\
& = &
\B'(\bx{2} + \bx{})
\end{eqnarray*}
are a fooling pair to $\B''$, 
as needed.
\end{proof} 



%===========================================
%===========================================
\section{Null Vectors}
\label{null vectors -- appendix}

We present some additional properties 
of null vectors
which complement the properties 
presented in Section \ref{null vectors}.
These new properties are of general interest
and give further insight for null vectors.

From the discussion of Section~\ref{null vectors}
we know that the null vectors form an equivalence class. 
Therefore,
we can immediately state the following transitive property
of null vectors.


\begin{lemma}
\label{immediate property}
Consider a balancing network 
$\B: \bx{} 
     \to 
     \by{}$.
Take any input vectors
$\bx{1}$ and
$\bx{2}$
that are a fooling pair to network $\B$.
Assume that
$\bx{2}$
is a null vector to network $\B$.
Then
$\bx{1}$
is also a null vector
to network $\B$.
\end{lemma}


Another interesting property of null vectors is that when we add a
null vector to an arbitrary vector, then the null vector does not
alter the state of the network.  This is shown in the next result,
which is complementary to Proposition~\ref{null vector linearity}.

\begin{proposition}
\label{null vector linearity sum} 
Consider a balancing network $\B: \bx{} \to \by{}$.  Take any null
input vector $\bx{1}$ to network $\B$.  Then, for any input vector
$\bx{}$, the input vectors $\bx{1} + \bx{}$ and $\bx{}$ are a fooling
pair to network $\B$.
\end{proposition}

\begin{proof}
From Proposition~\ref{balancing fooling pair sum},
by taking $\bx{1}$ for $\bx{1}$,
$\bzeroin$ for $\bx{2}$,
and $\bx{}$ for $\bx{}$,
we have that the vectors
$\bx{1} + \bx{}$ and $\bzeroin + \bx{} = \bx{}$,
are a fooling pair to network $\B$, as needed.
\end{proof}

Next, we show that a multiple of a null vector
is still a null vector. 
This result is complementary to 
Proposition~\ref{multiple linearity}.

\begin{proposition}
\label{multiple linearity sum}
Consider a balancing network 
$\B: \bx{} 
     \to 
     \by{}$.
Take any input vector
$\bx{}$
that is null to $\B$.
Then, 
for any integer $k \geq 0$,
$k \bx{}$ is a null vector to $\B$.
\end{proposition}




\begin{proof}

We proceed by induction on $k$.
For the basis case 
where $k=0$, 
the claim holds trivially.
Assume inductively that
the claim holds for all integers $k'$ 
such that $k' \leq k-1$.

For the induction step, 
consider the integer $k$.
Clearly,
\begin{eqnarray*}
      k \bx{} 
& = & (k-1) \bx{} + \bx{}\, .
\end{eqnarray*}
By the induction hypothesis,
$(k-1) \bx{}$ is a null vector to $\B$.
We apply Proposition~\ref{null vector linearity sum}
by taking
$(k-1) \bx{}$ for $\bx{1}$ 
and $\bx{}$ for $\bx{}$,
to obtain that
the input vectors
$(k-1) \bx{} + \bx{} = k \bx{}$ 
and $\bx{}$
are a fooling pair to $\B$.
By assumption,
$\bx{}$ is a null vector to $\B$.
It follows, 
by Lemma~\ref{immediate property},
that $k \bx{}$ is 
a null vector to $\B$,
as needed.
\end{proof}

\end{document}
