Cheap and Secure Web Hosting Provider : See Now

What does it mean to have tokens at a state in a balancing network?

, , No Comments
Problem Detail: 

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?

Asked By : Charlie Parker

Answered By : Yuval Filmus

It seems that there is a typo – $s$ and $B$ represent the same thing. It looks like the original $s$ was changed to $B$, but the author of the question forgot to delete $s$.

The state of the network is the state of all balancers – which way they point.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49827

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback