I was learning what balancing networks are and at some point the art of multicore programming talks about balancers. The text book says:
A balancer is a simple switch with two input wires and two output wires, called the top and bottom wires (or sometimes the north and south wires). Tokens arrive on the balancer’s input wires at arbitrary times, and emerge on their output wires, at some later time. A balancer can be viewed as a toggle: given a stream of input tokens, it sends one token to the top output wire, and the next to the bottom, and so on, effectively balancing the number of tokens between the two wires
from the discussion above it would seem that a balancer simple has a state up and down and it alternates between them and send tokens up and down (depending what state it is). Consider how the figure in the textbook defines a balancer:
It says that no matter the order and time, the tokens are split (balanced) as equal as possible between the above wire and the bottom wire. Therefore, no matter how the wires arrive, the balancer should maintain the invariant that the difference between top and bottom is at most 1.
The issue that I have is that it seems to describe the balancer as a state machine than alternates between up and down, but such a machine wouldn't actually be able to properly balance. It has to have some sort of state counting how many tokens it has sent up and how many it has sent down (so that it can balance). The code presented by the book seems to do the alternating up and down (unless I misunderstood it):
It doesn't quite have a counter than makes sure that it maintains, the balancing invariant. If not, then how does it actually do it?
