The impact of randomization in smoothing networks

Abstract

We revisit smoothing networks[3], which are made up of balancers and wires. Tokens arrive arbitrarily on w input wires and propagate asynchronously through the network

each token gets service on the output wire it arrives at. The smoothness is the maximum discrepancy among the numbers of tokens arriving at the w output wires. We assume that balancers are oriented independently and uniformly at random. We present a collection of lower and upper bounds on smoothness, which are to some extent surprising: • The smoothness of a single block network[7] is lg lg w + Θ(1) (with high probability), where the additive constant is between -2 and 4. This tight bound improves vastly over the upper bound of O(√lg w) from[9], and it significantly improves our understanding of the smoothing properties of the block network. • Most significantly, the smoothness of the cascade of two block networks is no more than 16 (with high probability)

this is the first known randomized network with so small depth (2 lg w) and so good smoothness. The proof introduces some novel combinatorial and probabilistic structures and techniques which may be further applicable. This result demonstrates the full power of randomization in smoothing networks. • There is no randomized 1-smoothing network of width w and depth d that achieves 1-smoothness with probability better than d/w-1 In view of the deterministic 1-smoothing network in[14], this result implies the first separation between deterministic and randomized smoothing networks, which demonstrates an unexpected limitation of randomization: it can get to constant smoothness very easily, but after that, the progress to 1-smoothing is very limited. Copyright 2008 ACM.