1
$\begingroup$

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:

enter image description here

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):

enter image description here

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?

$\endgroup$
1
$\begingroup$

The book is correct, and the algorithm works as advertised. See if you can prove that it does. No explicit counting is necessary.

A very similar situation occurs for languages: $(ab)^*(a + \epsilon)$ is regular even though $\{ w : 0 \leq \#_a(w) - \#_b(w) \leq 1 \}$ is not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.