Why is the step property in a balancing network defined as it is?

Question

I was trying to understand why the equation $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ describes the step property in a balancing network?

First, recall $x_i$ to be the number of tokens a network gets as input and similarly $y_i$ to be the number of output tokens. Recall that a balancing network is just a network that distributes tokens to its output.

I was reading the art of multicore programming and in page 272 it says:

If the number of tokens n is a multiple of four (the network width), then the same number of tokens emerges from each wire. If there is one excess token, it emerges on output wire 0, if there are two, they emerge on output wires 0 and 1, and so on. In general,

$$ n = \sum x_i $$

then

$$y_i = \left( \frac{n}{w} \right) + (i \pmod w) $$

we call this property the step property.

It also defines equivalent ways to see the step property as:

1. For any $i<j$, $0 \leq y_i - y_j \leq 1$

i.e. as we go up the output wires, the wire can only increase one step at a time or not increase (so top values are always larger or equal). An example:

However, the formula $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ doesn't make sense to me also, specifically the following doesn't make sense:

if there are two, they emerge on output wires 0 and 1, and so on...

I tried plugging in the numbers too say, $ n = 6 $, but the results don't quite make sense.

For example according to the formula above we get:

$$ y_0 = \left( \frac{6}{4} \right) + (0 \pmod 4) = 1 + 0 = 1 $$ $$ y_1 = \left( \frac{6}{4} \right) + (1 \pmod 4) = 1 + 1 = 2 $$ $$ y_2 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 2 = 3 $$ $$ y_3 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 3 = 4 $$

which doesn't agree with what the picture of the diagram would be because it seems to be backwards. Not sure if I made a mistake or misunderstood the formula, but it should be giving something as in the figure/diagram/picture from the book. Also, according to the formula, is it ever possible for it be equal? It seems to always increase in the wrong direction.

Answer 1

The formula is wrong. The correct formula is $$ y_i = \lfloor \frac{n}{w} \rfloor + [i < (n \mod{w})], $$ where $[C]$ equals 1 if $C$ holds, and 0 otherwise.

Sometimes books contain mistakes. When you see a mistake, correct it and proceed. No need to ask us for permission.