I was assigned as homework:
Suppose we have a width-w balancing network of depth $d$ in a quiescent state $s$ called $B$. Let $n = 2^d$. Prove that if n tokens enter the network on the same wire, pass through the network, and exit, then $B$ will have the same state after the tokens exit as it did before they entered.
However, I do not understand what the question is asking (please don't actually do the problem).
I have followed chapter 12 of the art of mutlicore programming, and its still unclear what the question is asking. Let me give you my thoughts (and confusions):
What does it mean by $s$ and $B$? According to the textbook, a balancing network is quiescent if every token that arrived on an input wire has emerged on an output wire (which makes sense because we only care when the tokens pass the network, not their order). Does a quiescent state refer to which cables the tokens have entered? Or since the order doesn't matter it just means that the same number of tokens that entered left the network?
What do they refer to as "a state"? Does it means were the tokens are located and which wires they left or if we only care about quiescent states, that the total number of tokens at the beginning and the end is the same?