Supporting Increment and Decrement Operations in Balancing Networks^{∗}

William Aiello^{†}  Costas Busch^{‡}  Maurice Herlihy^{‡}
Marios Mavronicolas^{§}  Nir Shavit^{¶}  Dan Touitou^{∥}

February 13, 2001

Abstract

Counting networks are a class of distributed data structures that support highly concurrent implementations of shared 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 any counting network can be extended to support atomic decrements

∗This paper combines, unifies, and extends results appearing in preliminary form in [2] and [7]. A preliminary version of this paper appears in the Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS’99), pp. 377–386, Trier, Germany, March 1999.

†AT&T Labs, 180 Park Avenue, Florham Park, NJ 07932. Email:

aiello@research.att.com

‡Department of Computer Science, Brown University, Providence, RI 02915. Email:

{cb,mph}@cs.brown.edu

§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: mavronic@cs.ucy.ac.cy

¶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: shanir@theory.lcs.mit.edu

∥IDC Herzliya, Tel-Aviv, Israel. Email: danidin@math.tau.ac.il

in a simple and natural way. Moreover, we identify a broad class of network 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.

1 Introduction

1.1 Motivation-Overview

Counting networks were originally introduced by Aspnes et al. [4] and subsequently extended in [1, 14, 16]. They are designed to provide highly concurrent implementations of shared Fetch&Increment counters, shared pools and stacks, load balancing modules, and software barriers (see, e.g., [4, 17, 19, 24]).

Counting networks are constructed from basic computing elements called balancers. On an abstract level, a balancer can be thought of as a routing switch for elements called tokens. It has a collection of input wires and a collection of output wires, respectively called the balancer’s fan-in and fanout. 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 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 step property [4]: if y_{i} tokens exit on output wire i, then 0 ≤ y_{i} − y_{j} ≤ 1 for any j > i.

A 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 comparator networks are constructed from comparators [10, Chapter 28]. 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 K-smoothing network [1, 4] 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 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 ≤ y_{i} − y_{j} ≤ 1 for any j > i. Counting networks can be used to implement Fetch&Increment counters: the l-th token (where l = 0, 1, …) to exit on output wire j returns the value j + l · w_{out}, where w_{out} 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 semaphores [13], critical-regions [18], and monitors [15] all rely on applying both increment and decrement operations on shared counters for both correctness and efficiency (see, e.g., [26, Chapter 6]). Moreover, several concurrent algorithms for classical multiprocessor synchronization problems such as the mutual exclusion problem [12] and the readers-writers problem [11], involve coordination by incrementing and decrementing of shared counters.

Shavit and Touitou [24] 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 antitoken.^{∗} 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 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 counting trees [25] satisfy the gap step property when traversed by tokens and antitokens.

Shavit and Touitou [24] 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 arbitrary counting networks. ^{†} 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.

∗The name was actually suggested by Yehuda Afek (personal communication).

• 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 any counting network can be extended to support a Fetch&Decrement operation.

• Any counting network, not just elimination trees, permits tokens and antitokens to eliminate one another when implementing a concurrent pool.

• 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.

• More generally, we identify a broad class of properties, which we call 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.

An interesting aspect of our work is that, unlike [24], our proofs are combinatorial, not operational. They rely on the novel concept of a fooling pair of input vectors, which we believe is of independent interest.

1.2 Our Techniques and Main Result

Aspnes et al. [4] introduced the convention of assigning the value 1 to each token, a convention maintained by later constructions [1, 5, 9, 14, 16, 20, 21, 25]. Shavit and Touitou [24] 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.

†This is especially so since efficient (low contention) implementations of tree-shaped counting networks require the use of randomized “diffraction” mechnisms [25], which cannot be “hardwired.” Having a hardwired (fixed layout) network is significant for hardware implementations, and for systems with real-time constraints.

Generalizing the approach taken by Aspnes et al. [4], we represent a balancer as an “operator” carrying an integer input vector to an integer output vector. The i-th entry in the input vector represents the 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 nonnegative, 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 property of a balancing network. A boundedness property satisfies two conditions:

• it is a subset of the K-smoothing property, for some K ≥ 1, and

• it is closed under the addition of any constant vector.

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, 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 state of any given balancer, viewed as a toggle mechanism, be the “position” of its toggle. Two input vectors are a 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 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 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 2 provides a framework for our discussion. In Section 3 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 4, and null vectors are treated in Section 5. Section 6 presents our main result. We conclude in Section 7 with a discussion and some open problems. (In Appendices A and B, you can find some additional properties for fooling pairs and null vectors which are of general interest.)

2 Framework

In this section, we present some general definitions, which extend those in [1, 9, 14, 16] to account for both tokens and antitokens; they somehow simplify and formalize corresponding ones in [24]. It is organized as follows. Subsection 2.1 specifies some notation. Balancers and balancing networks are introduced in Subsections 2.2 and 2.3, respectively. Sectionsection 2.4 treats boundedness properties.

2.1 Notation

For any integer g ≥ 2, x^{(g)} denotes the vector ⟨x_{0}, x_{1}, …, x_{g−1}⟩^{T}. For any vector x^{(g)}, denote ∥x^{(g)}∥_{1} = ∑_{i=0}^{g−1} x_{i}. We use 0^{(g)} to denote ⟨0, 0, …, 0⟩^{T}, a vector with g zero entries. A constant vector is any vector in which each entry is equal to some constant c. We say that a vector is non-negative if all of its entries are non-negative integers.

For any integer x and positive integer δ, denote x div δ and x mod δ the integer quotient and remainder, respectively, of the division of x by δ; note that 0 ≤ x mod δ ≤ δ − 1 and x = (x div δ) δ + x mod δ. Say that δ divides vector x^{(g)} if δ divides each entry of x^{(g)} (without leaving remainder).

1 4 3 2 7

6

8

9 1 2

3 4 5 6 7 9

8

x_{0}
x_{1}
x_{2}

y_{0}
y_{1}
y_{2}
y_{3}
y_{4}

-2 0

0 0 -1 -1 -1 5 -1

Figure 1: A balancer

2.2 Balancers

Balancing networks are constructed from acyclically wired elements, called balancers, that route tokens and antitokens through the network, and wires. For the sake of generality, our balancers are defined as “multibalancers,” in the style of Aharonson and Attiya [1], Felten et al. [14], and Hardavellas et al. [16]; however, we follow Shavit and Touitou [24] 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 f_{in} and f_{out}, an (f_{in}, f_{out})-balancer, or balancer for short, is a routing element receiving tokens and antitokens on f_{in} input wires, numbered 0, 1, …, f_{in} − 1, and sending out tokens and antitokens to f_{out} output wires, numbered 0, 1, …, f_{out} − 1; f_{in} and f_{out} are called the balancer’s fan-in and 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” 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 1 depicts a balancer with three input wires and five output wires, stretched horizontally; the balancer is stretched vertically. In the left part, tokens and antitokens are denoted with full and empty circles, respectively; the numbering in the tokens and antitokens reflects the realtime 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 ≤ i < f_{in}, we denote by x_{i} the 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 minus the number of antitokens that have entered. Denote x^{(f_{in})} = ⟨x_{0}, x_{1}, …, x_{f_{in}−1}⟩^{T}; call x^{(f_{in})} an input vector. For each output index j, 0 ≤ j < f_{out}, we denote by y_{j} the 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 minus the number of antitokens that have exited on output wire j. The right part of Figure 1 shows the corresponding input and output state variables. Denote by y^{(f_{out})} = ⟨y_{0}, y_{1}, …, y_{f_{out}−1}⟩^{T} the corresponding output vector.

The configuration of a balancer at any given time is the tuple ⟨x^{(f_{in})}, y^{(f_{out})}⟩; roughly speaking, the configuration is the collection of its input and output state variables. In the initial configuration, all input and output wires are empty; hence, in the initial configuration, x^{(f_{in})} = 0^{(f_{in})}, and y^{(f_{out})} = 0^{(f_{out})}. A configuration of a balancer is 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 (f_{in}, f_{out})-balancer.

1. Safety property: in any configuration, a balancer never creates either tokens or antitokens spontaneously.

2. 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 ≤ e ≤ min{t, a}, is the number of tokens and antitokens that are “eliminated” in the balancer.

3. Step property: in any quiescent configuration, for any pair of output indices j and k such that 0 ≤ j < k < f_{out}, 0 ≤ y_{j} − y_{k} ≤ 1.

From the safety and liveness properties it follows, for any quiescent configuration ⟨x^{(f_{in})}, y^{(f_{out})}⟩ of a balancer, that ∥x^{(f_{in})}∥_{1} = ∥y^{(f_{out})}∥_{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 x^{(f_{in})}, denote y^{(f_{out})} = b(x^{(f_{in})}), the output vector in the quiescent configuration that b will reach after all ∥x^{(f_{in})}∥_{1} tokens and antitokens that entered b have exited; write also b : x^{(f_{in})} → y^{(f_{out})} to denote the balancer b. From the step property, for each 0 ≤ i < f_{out}, each entry y_{i} of the output vector y^{(f_{out})} can be written [1, 4, 9] as

y_{i} = ⌈\frac{∥x^{(f_{in})}∥_{1} − i}{f_{out}} ⌉ .

For any quiescent configuration ⟨x^{(f_{in})}, y^{(f_{out})}⟩ of a balancer b : x^{(f_{in})} → y^{(f_{out})}, the state of the balancer b, denoted state_{b}(⟨x^{(f_{in})}, y^{(f_{out})}⟩) is defined to be

state_{b}(⟨x^{(f_{in})}, y^{(f_{out})}⟩) = ∥x^{(f_{in})}∥_{1} mod f_{out} ;

since the configuration is quiescent, it follows that

state_{b}(⟨x^{(f_{in})}, y^{(f_{out})}⟩) = ∥y^{(f_{out})}∥_{1} mod f_{out} .

For the sake of simplicity we will denote

state_{b}(x^{(f_{in})}) = state_{b}(⟨x^{(f_{in})}, y^{(f_{out})}⟩) .

We remark that the state of an (f_{in}, f_{out})-balancer is an integer in the set {0, 1, …, f_{out} − 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 initial state. Note that the initial state of the balancer is 0.

2.3 Balancing Networks

A (w_{in}, w_{out})-balancing network B is a collection of interwired balancers, where output wires are connected to input wires, having w_{in} designated input wires, numbered 0, 1, …, w_{in} −1, which are not connected to output wires of balancers, having w_{out} designated output wires, numbered 0, 1, …, w_{out} −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. Figure 2 depicts a balancing network with eight input wires and twelve output wires, using the same conventions as in Figure 1.

For each input index i, 0 ≤ i < w_{in}, we denote by x_{i} the 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

0 0 0 0 0 0 -1 -1 -1 -1 -1 -11 5 3

8 15 -8 -7 -3 -4 -3 -3 12 11 -7 -8 -3

-3 -3

-4 3

2 2

1 0

0

0 0

0

-1 -1 0

0

-1 -1

-1 0

-1 0

-1 0

0

0

0 0

-1

-1

-1 0

-1 0

0 0

-1 0

0 -1

-1 x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7}

y_{0}
y_{1}
y_{2}
y_{3}
y_{4}
y_{5}
y_{6}
y_{7}
y_{8}
y_{9}
y_{10}
y_{11}

0

-1

-10 x_{0}

Figure 2: A balancing network

between the number of tokens and antitokens that have entered on input wire i. Denote x^{(w_{in})} = ⟨x_{0}, x_{1}, …, x_{w_{in}−1}⟩^{T}; call x^{(w_{in})} an input vector. For each output index j, 0 ≤ j < w_{out}, we denote by y_{j} the 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 minus the number of antitokens that have exited on output wire i. Denote y^{(w_{out})} = ⟨y_{0}, y_{1}, …, y_{w_{in}−1}⟩^{T}; call y^{(w_{out})} an output vector.

The configuration of a network at any given time is the tuple of configurations of its individual balancers. In the 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 quiescent configuration in which all tokens and antitokens that entered the network have exited. In any quiescent configuration of B we have ∥x^{(w_{in})}∥_{1} = ∥y^{(w_{out})}∥_{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 x^{(w_{in})} and y^{(w_{out})}, respectively, the state of B, denoted state_{B}(x^{(w_{in})}), is defined to be the collection of the states of its individual balancers. We remark that we have specified x^{(w_{in})} as the single argument of state_{B}, since x^{(w_{in})} 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 initial state. Note that the initial state of the network is a collection of 0s. For any input vector x^{(w_{in})}, denote by y^{(w_{out})} = B(x^{(w_{in})}) the output vector in the quiescent configuration that B will reach after all ∥x^{(w_{in})}∥_{1} tokens and antitokens that entered B have exited; write also B : x^{(w_{in})} → y^{(w_{out})} to denote the network B.

Not all balancing networks satisfy the step property. A (w_{in}, w_{out})- counting network is a (w_{in}, w_{out})-balancing network for which, in any quiescent configuration, for any pair of indices j and k such that 0 ≤ j < k < w_{out}, 0 ≤ y_{j} − y_{k} ≤ 1. In other words, the output of a counting network has the step property. For example, the network depicted in Figure 2 is a counting network [9], 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 [1, 4]. For any integer K ≥ 1, a (w_{in}, w_{out})-K-smoothing network is a (w_{in}, w_{out})- balancing network for which, in any quiescent configuration, for any pair of indices j and k such that 0 ≤ j, k < w_{out}, 0 ≤ |y_{j} − y_{k}| ≤ K; that is, the output vector of a K-smoothing network has the K-smoothing property: all outputs are within K of each other.

For a balancing network B, the depth of B, denoted depth(B), is defined to be the maximum distance from any of its input wires to any of its output wires. In case depth(B) = 1, B will be called a layer. If depth(B) = d is greater than one, then B can be uniquely partitioned into layers B_{1}, B_{2}, …, B_{d} from left to right in the obvious way.

2.4 Boundedness Properties

Fix any integer g ≥ 2. For any integer K ≥ 1, the K-smoothing property [1] is defined to be the set of all vectors y^{(g)} such that for any entries y_{j} and y_{k} of y^{(g)}, where 0 ≤ j, k < g, |y_{j} − y_{k}| ≤ K. A boundedness property is any subset of some K-smoothing property, for any integer K ≥ 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 y^{(g)} that have the step property [4] 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 Ksmoothing 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 a vector y has the boundedness property Π if y ∈ Π. Say that a balancing network B : x^{(w_{in})} → y^{(w_{out})} has the boundedness property Π if for every input vector x^{(w_{in})}, B(x^{(w_{in})}) ∈ Π.

3 A Simple Proof for Regular Networks

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, w_{in} = w_{out}), and the network consists from balancers with equal fan-in and fan-out (namely, f_{in} = f_{out} to each balancer). Regular networks appear in [1, 4, 6, 14].

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.

Lemma 3.1 Consider a regular balancing network B : x^{(w)} → y^{(w)}. Let z^{(w)} be any constant input vector. Then,

B(z^{(w)}) = z^{(w)} .  (1)

Proof: Since vector z^{(w)} is constant, there is a constant c such that z_{i} = c, for all 0 ≤ 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 ≤ i < w,

(B(z^{(w)}))_{i} = (b(z^{(w)}))_{i}
= ⌈\frac{∥z^{(w)}∥_{1} − i}{w}⌉
= ⌈\frac{c · w − i}{w}⌉
= ⌈c − \frac{i}{w} ⌉
= c + ⌈−\frac{i}{w} ⌉
= c ,

and thus, B(z^{(w)}) = z^{(w)}.

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 x^{(w)}, B(x^{(w)}) = B′′(B′(x^{(w)})).

We continue with the induction step. We have, B(z^{(w)}) = B′′(B′(z^{(w)})). From the induction hypothesis for network B′, we have B′(z^{(w)}) = z^{(w)}. Subsequently, B′′(B′(z^{(w)})) = B′′(z^{(w)}). From the induction hypothesis for B′′ we have, B′′(z^{(w)}) = z^{(w)}. Subsequently, B(z^{(w)}) = z^{(w)}, as needed.

Lemma 3.2 Consider a regular balancing network B : x^{(w)} → y^{(w)}. Let z^{(w)} be any constant input vector, and x^{(w)} be an arbitrary input vector. Then,

B(z^{(w)} + x^{(w)}) = B(z^{(w)}) + B(x^{(w)}) .  (2)

Proof: Since vector z^{(w)} is constant, there is a constant c such that z_{i} = c, for all 0 ≤ 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 ≤ i < w,

(B(z^{(w)} + x^{(w)}))_{i} = (b(z^{(w)} + x^{(w)}))_{i}
= ⌈\frac{∥z^{(w)} + x^{(w)}∥_{1} − i}{w}⌉

= ⌈\frac{∥z^{(w)}∥_{1} + ∥x^{(w)}∥_{1} − i}{w}⌉

= ⌈\frac{c · w + ∥x^{(w)}∥_{1} − i}{w}⌉

= ⌈c + \frac{∥x^{(w)}∥_{1} − i}{w}⌉

= c + ⌈\frac{∥x^{(w)}∥_{1} − i}{w}⌉
= c + (b(x^{(w)}))_{i}
= z_{i} + (B(x^{(w)}))_{i}
= (B(z^{(w)}))_{i} + (B(x^{(w)}))_{i} ,

(by Lemma 3.1)

and thus, B(z^{(w)} + x^{(w)}) = B(z^{(w)}) + B(x^{(w)}).

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,

B(z^{(w)} + x^{(w)}) = B′′(B′(z^{(w)} + x^{(w)})) .

From the induction hypothesis for network B′, we have,

B′(z^{(w)} + x^{(w)}) = B′(z^{(w)}) + B′(x^{(w)}) ,

and by Lemma 3.1, we obtain

B′(z^{(w)} + x^{(w)}) = z^{(w)} + B′(x^{(w)}) .

Subsequently,

B′′(B′(z^{(w)} + x^{(w)})) = B′′(z^{(w)} + B′(x^{(w)}))
= B′′(z^{(w)}) + B′′(B′(x^{(w)}))

(by the induction hypothesis for B′′)

= z^{(w)} + B(x^{(w)})
= B(z^{(w)}) + B(x^{(w)}) ,

(by applying Lemma 3.1 twice)

and it follows that B(z^{(w)} + x^{(w)}) = B(z^{(w)}) + B(x^{(w)}), as needed.

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

Theorem 3.3 Fix any boundedness property Π. Consider any regular balancing network B : x^{(w)} → y^{(w)} such that the output vector y^{(w)} has the boundedness property Π whenever the input vector x^{(w)} is non-negative. Then, B has the boundedness property Π.

Proof: Assume that B has the boundedness property Π for non-negative input vectors. Let x^{(w)} be an arbitrary input vector (which may contain negative entries). We will show that B(x^{(w)}) ∈ Π.

Construct from vector x^{(w)}, a constant vector z^{(w)} so that the vector z^{(w)} + x^{(w)} is non-negative (z^{(w)} could simply consist from the absolute value of the smallest entry of x^{(w)}). By Lemma 3.2, we have

B(x^{(w)}) = B(z^{(w)} + x^{(w)}) − B(z^{(w)}) .

Subsequently, by Lemma 3.1, we obtain

B(x^{(w)}) = B(z^{(w)} + x^{(w)}) − z^{(w)} .

Since the vector z^{(w)} + x^{(w)} is non-negative, we have from hypothesis that

B(z^{(w)} + x^{(w)}) ∈ Π .

Furthermore, since Π is a boundedness property, Π is closed under the addition with a constant vector, and since z^{(w)} is a constant vector, it follows that

B(z^{(w)} + x^{(w)}) + z^{(w)} ∈ Π .

Therefore, B(x^{(w)}) ∈ Π, as needed.

We want to note here that the proof of Theorem 3.3, holds only for regular balancing networks. The reason for this is that Lemmas 3.1 and 3.2, 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, w_{in} ≠ w_{out}).

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

Therefore, we need to take a different approach for general balancing networks. In Sections 4, and 5, we will identify the class of input vectors for which properties like the ones in Lemmas 3.1 and 3.2 hold for general balancing networks. Using these new kinds of vectors, we prove in section 6, our main result for general networks.

4 Fooling Pairs

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

Say that input vectors x_{1}^{(f_{in})} and x_{2}^{(f_{in})} are a fooling pair to balancer b : x^{(f_{in})} → y^{(f_{out})} if

state_{b}(x_{1}^{(f_{in})}) = state_{b}(x_{2}^{(f_{in})}) ;

roughly speaking, a fooling pair transitions the balancer to identical states in the two corresponding quiescent configurations. We start by showing:

Proposition 4.1 Consider a balancer b : x^{(f_{in})} → y^{(f_{out})}. Take any input vectors x_{1}^{(f_{in})} and x_{2}^{(f_{in})} that are a fooling pair to balancer b. Then, for any input vector x^{(f_{in})},

b(x_{1}^{(f_{in})} + x^{(f_{in})}) − b(x_{1}^{(f_{in})}) = b(x_{2}^{(f_{in})} + x^{(f_{in})}) − b(x_{2}^{(f_{in})}) .

Proof: Since the output of balancer b satisfies the step property, we have for each entry i, where 0 ≤ i < f_{out}, of vector b(x_{1}^{(f_{in})} + x^{(f_{in})}) − b(x_{1}^{(f_{in})}),

(b(x_{1}^{(f_{in})} + x^{(f_{in})}) − b(x_{1}^{(f_{in})}))_{i}
= ⌈\frac{∥x_{1}^{(f_{in})} + x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ − ⌈\frac{∥x_{1}^{(f_{in})}∥_{1} − i}{f_{out}}⌉

= ⌈\frac{∥x_{1}^{(f_{in})}∥_{1} + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ − ⌈\frac{∥x_{1}^{(f_{in})}∥_{1} − i}{f_{out}}⌉

= ⌈\frac{(∥x_{1}^{(f_{in})}∥_{1} div f_{out}) · f_{out} + (∥x_{1}^{(f_{in})}∥_{1} mod f_{out}) + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ −

⌈\frac{(∥x_{1}^{(f_{in})}∥_{1} div f_{out}) · f_{out} + (∥x_{1}^{(f_{in})}∥_{1} mod f_{out}) − i}{f_{out}}⌉

= ⌈(∥x_{1}^{(f_{in})}∥_{1} div f_{out}) + \frac{state_{b}(x_{1}^{(f_{in})}) + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ −

⌈(∥x_{1}^{(f_{in})}∥_{1} div f_{out}) + \frac{state_{b}(x_{1}^{(f_{in})}) − i}{f_{out}}⌉

(by definition of state_{b})

= (∥x_{1}^{(f_{in})}∥_{1} div f_{out}) + ⌈\frac{state_{b}(x_{1}^{(f_{in})}) + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ −

(∥x_{1}^{(f_{in})}∥_{1} div f_{out}) − ⌈\frac{state_{b}(x_{1}^{(f_{in})}) − i}{f_{out}}⌉

= ⌈\frac{state_{b}(x_{1}^{(f_{in})}) + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ − ⌈\frac{state_{b}(x_{1}^{(f_{in})}) − i}{f_{out}}⌉ .

Similarly, we can show that

(b(x_{2}^{(f_{in})} + x^{(f_{in})}) − b(x_{2}^{(f_{in})}))_{i}
= ⌈\frac{state_{b}(x_{2}^{(f_{in})}) + ∥x^{(f_{in})}∥_{1} − i}{f_{out}}⌉ − ⌈\frac{state_{b}(x_{2}^{(f_{in})}) − i}{f_{out}}⌉ .

Since x_{1}^{(f_{in})} and x_{2}^{(f_{in})} are a fooling pair to b, state_{b}(x_{1}^{(f_{in})}) = state_{b}(x_{2}^{(f_{in})}). It follows that

b(x_{1}^{(f_{in})} + x^{(f_{in})}) − b(x_{1}^{(f_{in})}) = b(x_{2}^{(f_{in})} + x^{(f_{in})}) − b(x_{2}^{(f_{in})}) ,

as needed.

We continue to extend the concept of a fooling pair from a single balancer to a network. Say that input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} are a fooling pair to network B : x^{(w_{in})} → y^{(w_{out})} if for each balancer b of B, the input vectors of b in quiescent configurations corresponding to x_{1}^{(w_{in})} and x_{2}^{(w_{in})}, 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 4.1 to the case of a balancing network.

Proposition 4.2 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} that are a fooling pair to network B. Then, for any input vector x^{(w_{in})},

B(x_{1}^{(w_{in})} + x^{(w_{in})}) − B(x_{1}^{(w_{in})}) = B(x_{2}^{(w_{in})} + x^{(w_{in})}) − B(x_{2}^{(w_{in})}) .

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 4.1 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′ : x^{(w_{in})} → z^{(w_{med})} and B′′ : z^{(w_{med})} → y^{(w_{out})} are networks of depth at most d − 1; that is, B is the “cascade” of B′ and B′′. Obviously, for any input vector x^{(w_{in})}, B(x^{(w_{in})}) = B′′(B′(x^{(w_{in})})).

We continue with the induction step. Since the input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} are a fooling pair to B, it follows that they are a fooling pair to B′. So, by induction hypothesis for B′,

B′(x_{1}^{(w_{in})} + x^{(w_{in})}) = B′(x_{1}^{(w_{in})}) + B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})}) .

Thus,

B(x_{1}^{(w_{in})} + x^{(w_{in})}) − B(x_{1}^{(w_{in})})
= B′′(B′(x_{1}^{(w_{in})} + x^{(w_{in})})) − B′′(B′(x_{1}^{(w_{in})}))
= B′′(B′(x_{1}^{(w_{in})}) + B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})})) − B′′(B′(x_{1}^{(w_{in})})) .

Since the input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} are a fooling pair to B, it follows that the vectors B′(x_{1}^{(w_{in})}) and B′(x_{2}^{(w_{in})}) are a fooling pair to B′′. Thus, we apply induction hypothesis for B′′ by taking B′(x_{1}^{(w_{in})}) for x_{1}^{(w_{in})}, B′(x_{2}^{(w_{in})}) for x_{2}^{(w_{in})}, and B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})}) for x^{(w_{in})}, to obtain that

B′′(B′(x_{1}^{(w_{in})}) + B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})})) − B′′(B′(x_{1}^{(w_{in})}))

= B′′(B′(x_{2}^{(w_{in})}) + B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})})) − B′′(B′(x_{2}^{(w_{in})}))
= B′′(B′(x_{2}^{(w_{in})} + x^{(w_{in})})) − B′′(B′(x_{2}^{(w_{in})}))
= B(x_{2}^{(w_{in})} + x^{(w_{in})}) − B(x_{2}^{(w_{in})}) .

It follows that B(x_{1}^{(w_{in})} + x^{(w_{in})}) − B(x_{1}^{(w_{in})}) = B(x_{2}^{(w_{in})} + x^{(w_{in})}) − B(x_{2}^{(w_{in})}), as needed.

In Appendix A, we present some additional properties for fooling pairs, which are of general interest and give further insight into fooling pairs.

5 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 null vectors, whose associated state is identical to the initial state of the network.

Formally, we say that x^{(w_{in})} is a null vector to network B : x^{(w_{in})} → y^{(w_{out})} if the vectors x^{(w_{in})} and 0^{(w_{in})} 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.

Proposition 5.1 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any null input vector x_{1}^{(w_{in})} to network B. Then, for any input vector x^{(w_{in})},

B(x_{1}^{(w_{in})} + x^{(w_{in})}) = B(x_{1}^{(w_{in})}) + B(x^{(w_{in})}) .

Proof: From Proposition 4.2, by taking x_{1}^{(w_{in})} for x_{1}^{(w_{in})}, 0^{(w_{in})} for x_{2}^{(w_{in})}, and x^{(w_{in})} for x^{(w_{in})}, we have,

B(x_{1}^{(w_{in})} + x^{(w_{in})}) − B(x_{1}^{(w_{in})}) = B(0^{(w_{in})} + x^{(w_{in})}) − B(0^{(w_{in})})
= B(x^{(w_{in})}) − 0^{(w_{out})}
(since B(0^{(w_{in})}) = 0^{(w_{out})})
= B(x^{(w_{in})}) .

Therefore, B(x_{1}^{(w_{in})} + x^{(w_{in})}) = B(x_{1}^{(w_{in})}) + B(x^{(w_{in})}), as needed.

We continue to show:

Proposition 5.2 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any input vector x^{(w_{in})} that is null to B. Then, for any integer k ≥ 0,

B(kx^{(w_{in})}) = kB(x^{(w_{in})}) .

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′ ≤ k − 1. For the induction step, consider the integer k. Clearly,

kx^{(w_{in})} = x^{(w_{in})} + (k − 1)x^{(w_{in})} ,

so that

B(kx^{(w_{in})}) = B(x^{(w_{in})} + (k − 1)x^{(w_{in})}) .

We apply Proposition 5.1 by taking x^{(w_{in})} for x_{1}^{(w_{in})} and (k − 1)x^{(w_{in})} for x^{(w_{in})}, to obtain that

B(x^{(w_{in})} + (k − 1)x^{(w_{in})}) = B(x^{(w_{in})}) + B((k − 1)x^{(w_{in})})
= B(x^{(w_{in})}) + (k − 1)B(x^{(w_{in})})

(by induction hypothesis)

= kB(x^{(w_{in})}) .

Therefore, B(kx^{(w_{in})}) = kB(x^{(w_{in})}), as needed.

For any balancing network B, denote by W_{out}(B) the product of the fanouts of balancers of B. The next claim establishes a sufficient condition for null vectors.

Proposition 5.3 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Assume that W_{out}(B) divides x^{(w_{in})}. Then x^{(w_{in})} is a null vector to B.

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 : x^{(f_{in})} → y^{(f_{out})} of B. By definition of W_{out}(B), f_{out} divides W_{out}(B). Since W_{out}(B) divides x^{(w_{in})}, it follows that f_{out} divides x^{(w_{in})}. Hence, f_{out} divides the restriction x^{(f_{in})} of x^{(w_{in})} so that x^{(f_{in})} is a null vector to b. Since b was chosen arbitrarily, this implies that x^{(w_{in})} 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 W_{out}(B) divides x^{(w_{in})} and W_{out}(B) = W_{out}(B′)W_{out}(B′′), it follows that W_{out}(B′) divides x^{(w_{in})}. By the induction hypothesis for network B′, it now follows that x^{(w_{in})} is a null vector to network B′.

It remains to be shown that B′(x^{(w_{in})}) is a null vector to network B′′. Since W_{out}(B′′) divides x^{(w_{in})}, Proposition 5.2 for B′ (by taking W_{out}(B′′) for k, and x^{(w_{in})}/W_{out}(B′′) for x^{(w_{in})}), implies that W_{out}(B′′) divides B′(x^{(w_{in})}). Thus, by induction, the hypothesis for network B′′, B′(x^{(w_{in})}) is a null vector to network B′′, which completes the proof.

In Appendix B, we present some additional properties for null vectors which are of general interest, and give further insight into null vectors.

6 Equivalence

In this section, we show our main equivalence result. We start by proving:

Proposition 6.1 Fix any boundedness property Π. Consider any balancing network B : x^{(w_{in})} → y^{(w_{out})} that has the boundedness property Π whenever the input vector x^{(w_{in})} is non-negative. Assume that x^{(w_{in})} is a null nonnegative input vector. Then, the respective output vector y^{(w_{out})} is constant.

Proof: Assume, by way of contradiction, that there exist entries y_{j} and y_{k} of y^{(w_{out})} such that y_{j} ≠ y_{k}. Clearly, |y_{j} − y_{k}| ≥ 1.

Since B has the boundedness property, it follows that |y_{j} − y_{k}| ≤ K for some universal integer K ≥ 1.

Since x^{(w_{in})} is a null vector, it follows by Proposition 5.2, that

B((K + 1)x^{(w_{in})}) = (K + 1)B(x^{(w_{in})})
= (K + 1)y^{(w_{out})} .

Since (K + 1)x^{(w_{in})} 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)y^{(w_{out})} has the boundedness property Π. Subsequently, for the jth and kth entries y′_{j} and y′_{k}, respectively, of (K +1)y^{(w_{out})}, we have

|y′_{j} − y′_{k}| ≤ K .

However,

y′_{j} − y′_{k} = (K + 1)y_{j} − (K + 1)y_{k}
= (K + 1)(y_{j} − y_{k}) ,

so that

|y′_{j} − y′_{k}| = (K + 1)|y_{j} − y_{k}|
≥ K + 1 ,

a contradiction.

We finally show our main result:

Theorem 6.2 Fix any boundedness property Π. Consider any balancing network B : x^{(w_{in})} → y^{(w_{out})} such that y^{(w_{out})} has the boundedness property Π whenever the input vector x^{(w_{in})} is non-negative. Then, B has the boundedness property Π.

Proof: Consider any arbitrary input vector x^{(w_{in})}. We will show that B(x^{(w_{in})}) has the boundedness property Π.

Construct from x^{(w_{in})} an input vector x̃^{(w_{in})} such that for each index i, 0 ≤ i < w_{in}, x̃_{i} is the least multiple of W_{out}(B) such that x̃_{i} + x_{i} ≥ 0. Clearly, both vectors x̃^{(w_{in})} and x̃^{(w_{in})} + x^{(w_{in})} are non-negative. Furthermore, W_{out}(B) divides x̃^{(w_{in})}, and therefore, by Proposition 5.3, we have that x̃^{(w_{in})} is a null vector. Since x̃^{(w_{in})} is non-negative, by Proposition 6.1, we have that B(x̃^{(w_{in})}) is a constant vector. We apply Proposition 5.1 with x̃^{(w_{in})} for x_{1}^{(w_{in})}, and x^{(w_{in})} for x^{(w_{in})}; we obtain that

B(x̃^{(w_{in})} + x^{(w_{in})}) = B(x̃^{(w_{in})}) + B(x^{(w_{in})}) ,

so that

B(x^{(w_{in})}) = B(x̃^{(w_{in})} + x^{(w_{in})}) − B(x̃^{(w_{in})}) .

Since x̃^{(w_{in})} + x^{(w_{in})} is a non-negative input vector, it follows, by assumption on B, that B(x̃^{(w_{in})} + x^{(w_{in})}) has the boundedness property Π. Since B(x̃^{(w_{in})}) is a constant vector, it follows, by closure of the boundedness property under addition with a constant vector, that B(x^{(w_{in})}) has the boundedness property Π, as needed.

7 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 [1, 3, 4, 5, 9, 14, 16, 20, 21, 25] 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 [22, 23] immediately carry over when introducing antitokens in addition to tokens. Our work leaves open several interesting questions and problems.

Aiello et al. [3] present an interesting construction of a randomized counting network; they use 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 threshold property [4, 8] and the weak threshold property [8], outlined below. Let x^{(w_{in})} and y^{(w_{out})} 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} = ⌈∥x^{(w_{in})}∥_{1}/w_{out}⌉, while for the weak threshold property, we require that there is some output index j, possibly j ≠ 0, such that y_{j} = ⌈∥x^{(w_{in})}∥_{1}/w_{out}⌉. 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.

References

[1] E. Aharonson and H. Attiya. Counting networks with arbitrary fan-out. Distributed Computing, 8(4):163–169, 1995.

[2] W. Aiello, M. Herlihy, N. Shavit, and D. Touitou. Inc/dec counting networks. Manuscript, Dec. 1995.

[3] W. Aiello, R. Venkatesan, and M. Yung. Coins, weights and contention in balancing networks. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC’94), pages 193– 205, Los Angeles, Aug. 1994.

[4] J. Aspnes, M. Herlihy, and N. Shavit. Counting networks. Journal of the ACM, 41(5):1020–1048, Sept. 1994.

[5] C. Busch, N. Hardavellas, and M. Mavronicolas. Contention in counting networks (abstract). In Proceedings of the 13th annual ACM Symposium on Principles of Distributed Computing (PODC’94), page 404, Los Angeles, Aug. 1994.

[6] C. Busch and M. Herlihy. Sorting and counting networks of small-depth and arbitrary width. In Proceedings of the 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA’99), pages 64–73, Saint-Malo, France, June 1999.

[7] C. Busch and M. Mavronicolas. The strength of counting networks (abstract). In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC’96), page 311, Philadelphia, May 1996.

[8] C. Busch and M. Mavronicolas. Impossibility results for weak threshold networks. Information Processing Letters, 63(2):85–90, July 1997.

[9] C. Busch and M. Mavronicolas. An efficient counting network. In Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing (IPPS/SPDP’98), pages 380–385, Mar. 1998.

[10] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms. MIT Press and McGraw-Hill Book Company, Cambridge, MA, 1992.

[11] P. J. Courtois, F. Heymans, and D. L. Parnas. Concurrent control with “readers” and “writers”. Communications of the ACM, 14(10):667–668, Oct. 1971.

[12] E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 8(9):569, Sept. 1965.

[13] E. W. Dijkstra. Cooperating sequential processes. In Programming Languages, pages 43–112. Academic Press, 1968.

[14] E. W. Felten, A. LaMarca, and R. Ladner. Building counting networks from larger balancers. Technical Report TR 93-04-09, University of Washington, Apr. 1993.

[15] P. B. Hansen. Operating System Principles. Prentice-Hall, Englewood Cliffs, NJ, 1973.

[16] N. Hardavellas, D. Karakos, and M. Mavronicolas. Notes on sorting and counting networks. In Proceedings of the 7th International Workshop on Distributed Algorithms (WDAG’93), volume 725 of Lecture Notes in Computer Science, pages 234–248, Lausanne, Switzerland, Sept. 1993. Springer-Verlag.

[17] M. Herlihy, B.-H. Lim, and N. Shavit. Scalable concurrent counting. ACM Transactions on Computer Systems, 13(4):343–364, Nov. 1995.

[18] C. A. R. Hoare and R. N. Periott. Operating Systems Techniques. Academic Press (New York NY), London, 1972.

[19] S. Kapidakis and M. Mavronicolas. Distributed, low contention task allocation. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP’96), pages 358–365, Washington, Oct. 1996.

[20] M. Klugerman. Small-Depth Counting Networks and Related Topics. PhD thesis, Department of Mathematics, Massachusetts Institute of Technology, Sept. 1994.

[21] M. Klugerman and C. G. Plaxton. Small-depth counting networks. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (STOC’92), pages 417–428, Victoria, B.C., Canada, May 1992.

[22] N. Lynch, N. Shavit, A. Shvartsman, and D. Touitou. Counting networks are practically linearizable. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC’96), pages 280–289, New York, May 1996.

[23] M. Mavronicolas, M. Papatriantafilou, and P. Tsigas. The impact of timing on linearizability in counting networks. In Proceedings of the 11th International Parallel Processing Symposium (IPPS’97), pages 684–688, Los Alamitos, Apr. 1997.

[24] N. Shavit and D. Touitou. Elimination trees and the construction of pools and stacks. Theory of Computing Systems, 30(6):545–570, Nov./Dec. 1997.

[25] N. Shavit and A. Zemach. Diffracting trees. ACM Transactions on Computer Systems, 14(4):385–428, Nov. 1996.

[26] A. Silberschatz and P. B. Galvin. Operating System Concepts. Addison Wesley, 4th edition, 1994.

A Fooling Pairs

We present some additional properties of fooling pairs which complement the properties presented in Section 4.

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:

Lemma A.1 Consider a balancer b : x^{(f_{in})} → y^{(f_{out})}. Then, for any input vectors x_{1}^{(f_{in})} and x_{2}^{(f_{in})},

state_{b}(x_{1}^{(f_{in})} + x_{2}^{(f_{in})}) = (state_{b}(x_{1}^{(f_{in})}) + state_{b}(x_{2}^{(f_{in})})) mod f_{out} .

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 4.1.

Proposition A.2 Consider a balancer b : x^{(f_{in})} → y^{(f_{out})}. Take any input vectors x_{1}^{(f_{in})} and x_{2}^{(f_{in})} that are a fooling pair to balancer b. Then, for any input vector x^{(f_{in})}, the input vectors x_{1}^{(f_{in})} + x^{(f_{in})} and x_{2}^{(f_{in})} + x^{(f_{in})} are a fooling pair to balancer b.

Proof: Clearly, by Lemma A.1,

state_{b}(x_{1}^{(f_{in})} + x^{(f_{in})}) = (state_{b}(x_{1}^{(f_{in})}) + state_{b}(x^{(f_{in})})) mod f_{out} ,

and

state_{b}(x_{2}^{(f_{in})} + x^{(f_{in})}) = (state_{b}(x_{2}^{(f_{in})}) + state_{b}(x^{(f_{in})})) mod f_{out} .

Since x_{1}^{(f_{in})} and x_{2}^{(f_{in})} are a fooling pair to b, state_{b}(x_{1}^{(f_{in})}) = state_{b}(x_{2}^{(f_{in})}), and it follows that

state_{b}(x_{1}^{(f_{in})} + x^{(f_{in})}) = state_{b}(x_{2}^{(f_{in})} + x^{(f_{in})});

thus, x_{1}^{(f_{in})} + x^{(f_{in})} and x_{2}^{(f_{in})} + x^{(f_{in})} are a fooling pair to b, as needed.

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 4.2.

Proposition A.3 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} that are a fooling pair to network B. Then, for any input vector x^{(w_{in})}, the input vectors x_{1}^{(w_{in})}+x^{(w_{in})} and x_{2}^{(w_{in})}+ x^{(w_{in})} are a fooling pair to network B.

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 A.2 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′ : x^{(w_{in})} → z^{(w_{med})} and B′′ : z^{(w_{med})} → y^{(w_{out})} 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 x_{1}^{(w_{in})} and x_{2}^{(w_{in})} 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 x^{(w_{in})}, the input vectors x_{1}^{(w_{in})} + x^{(w_{in})} and x_{2}^{(w_{in})} + x^{(w_{in})} are a fooling pair to B′. It remains to be shown that the vectors B′(x_{1}^{(w_{in})}+x^{(w_{in})}) and B′(x_{2}^{(w_{in})}+x^{(w_{in})}) are a fooling pair to B′′.

By applying Proposition 4.2 to B′,

B′(x_{1}^{(w_{in})} + x^{(w_{in})}) − B′(x_{1}^{(w_{in})}) = B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})}) ,

while, by assumption, B′(x_{1}^{(w_{in})}) and B′(x_{2}^{(w_{in})}) are a fooling pair for B′′. We apply the induction hypothesis to B′′, taking B′(x_{1}^{(w_{in})}) for x_{1}^{(w_{in})}, B′(x_{2}^{(w_{in})}) for x_{2}^{(w_{in})}, and B′(x_{1}^{(w_{in})} + x^{(w_{in})}) − B′(x_{1}^{(w_{in})}) for x^{(w_{in})}; it implies that the input vectors

B′(x_{1}^{(w_{in})}) + B′(x_{1}^{(w_{in})} + x^{(w_{in})}) − B′(x_{1}^{(w_{in})})
= B′(x_{1}^{(w_{in})} + x^{(w_{in})}) ,

and

B′(x_{2}^{(w_{in})}) + B′(x_{1}^{(w_{in})} + x^{(w_{in})}) − B′(x_{1}^{(w_{in})})
= B′(x_{2}^{(w_{in})}) + B′(x_{2}^{(w_{in})} + x^{(w_{in})}) − B′(x_{2}^{(w_{in})})
= B′(x_{2}^{(w_{in})} + x^{(w_{in})})

are a fooling pair to B′′, as needed.

B Null Vectors

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

From the discussion of Section 5 we know that the null vectors form an equivalence class. Therefore, we can immediately state the following transitive property of null vectors.

Lemma B.1 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any input vectors x_{1}^{(w_{in})} and x_{2}^{(w_{in})} that are a fooling pair to network B. Assume that x_{2}^{(w_{in})} is a null vector to network B. Then x_{1}^{(w_{in})} is also a null vector to network B.

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 5.1.

Proposition B.2 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any null input vector x_{1}^{(w_{in})} to network B. Then, for any input vector x^{(w_{in})}, the input vectors x_{1}^{(w_{in})} + x^{(w_{in})} and x^{(w_{in})} are a fooling pair to network B.

Proof: From Proposition A.3, by taking x_{1}^{(w_{in})} for x_{1}^{(w_{in})}, 0^{(w_{in})} for x_{2}^{(w_{in})}, and x^{(w_{in})} for x^{(w_{in})}, we have that the vectors x_{1}^{(w_{in})} + x^{(w_{in})} and 0^{(w_{in})} + x^{(w_{in})} = x^{(w_{in})}, are a fooling pair to network B, as needed.

Next, we show that a multiple of a null vector is still a null vector. This result is complementary to Proposition 5.2.

Proposition B.3 Consider a balancing network B : x^{(w_{in})} → y^{(w_{out})}. Take any input vector x^{(w_{in})} that is null to B. Then, for any integer k ≥ 0, kx^{(w_{in})} is a null vector to B.

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′ ≤ k − 1.

For the induction step, consider the integer k. Clearly,

kx^{(w_{in})} = (k − 1)x^{(w_{in})} + x^{(w_{in})} .

By the induction hypothesis, (k − 1)x^{(w_{in})} is a null vector to B. We apply Proposition B.2 by taking (k − 1)x^{(w_{in})} for x_{1}^{(w_{in})} and x^{(w_{in})} for x^{(w_{in})}, to obtain that the input vectors (k − 1)x^{(w_{in})} + x^{(w_{in})} = kx^{(w_{in})} and x^{(w_{in})} are a fooling pair to B. By assumption, x^{(w_{in})} is a null vector to B. It follows, by Lemma B.1, that kx^{(w_{in})} is a null vector to B, as needed.