As witching network is a directed graph, where edges are called wires and nodes are called switches. Each thread shepherds at oken through the net-work. Switches and tokens are allowed to have internal states. A token arrives at as witch via an input wire. In one atomic step, the switch absorbs the token, changes its state and possibly the token’s state, and emits the token on an output wire. Here, for simplicity, switches have two input and output wires. Note that switching net works are more powerful than balancing networks, since switches can have arbitrary state(instead of a single bit) and tokens also have state. An adding network is a switching network that allows threads to add (or subtract)arbitrary values.
We say that a token is in front of a switch if it is on one of the switch’s input wires. Start with the network in a quiescent stateq0, where the next token to run will take value 0. Imagine we have one to kent of weight a and n–1 tokenst1,...,tn−1all of weight b, where b>a, each on a distinct input wire. Denote by S the set of switches that t traverses if it traverses the network by starting inq0.Prove that if we run thet1,...,tn−1one at a time though the network, we can hal teachti in front of a switch of S.At the end of this construction,n−1 tokens are in front of switches of S. Since switches have two input wires, it follows that t’s path through the network en com-passes at leastn−1 switches, so any adding network must have depth at leastn−1,wherenis the maximum number of concurrent tokens. This bound is discourage in g because it implies that the size of the network depends on the number of threads(also true for Combining Trees, but not counting networks), and that the network has inherently high latency.