A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced.

We study randomized smoothing networks, whose initial states are chosen at random. Randomized smoothing networks require no global initialization, and also require no global reconfiguration after faults.

This paper makes the following contributions. We show that the well-known block smoothing network (which is isomorphic to the butterfly network), when started in a random initial state, is 0(\sqrt {\log (w)})-smooth with high probability, where w is the number of input/output wires. We show that as a corollary, the bitonic and periodic networks are also 0(\sqrt {\log (w)})-smooth with high probability, when started in random initial states. In contrast, it is known that these networks are (log w)-smooth in the worst case.