The impact of randomization in smoothing networks

ABSTRACT

We revisit smoothing networks 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 is log log 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(√log w) from Herlihy and Tirthapura, 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 log 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 from Klugerman and Plaxton, 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.

REFERENCES

• 1: William Aiello , Ramarathnam Venkatesan , Moti Yung, Coins, weights and contention in balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.193-205, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198090]
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
• 4: K. E. Batcher,"Sorting Networks and their Applications," Proceedings of the AFIPS Joint Computer Conference, pp. 334--338, 1968.
• 5: An Efficient Counting Network, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.380, March 30-April 03, 1998
• 6: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 7: Martin Dowd , Yehoshua Perl , Larry Rudolph , Michael Saks, The periodic balanced sorting network, Journal of the ACM (JACM), v.36 n.4, p.738-757, Oct. 1989 [doi>10.1145/76359.76362]
• 8: M. Herlihy and N. Shavit, The Art of Multiprocessor Programming,Morgan Kaufmann/Elsevier, 2008.
• 9: Maurice Herlihy , Srikanta Tirthapura, Randomized smoothing networks, Journal of Parallel and Distributed Computing, v.66 n.5, p.626-632, May 2006 [doi>10.1016/j.jpdc.2005.06.009]
• 10: M. Herlihy and S. Tirthapura,"Self-Stabilizing Smoothing and Counting Networks," Distributed Computing,Vol. 18, pp. 345--357, 2006.
• 11: . Hoeffding.newblock "Probability Inequalities for Sums of Bounded Random Variables,"\newblock \textitJournal of the American Statistical Association, Vol. 53, pp. 13--30, 1963.
• 12: Distributed, Low Contention Task Allocation, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.358, October 23-26, 1996
• 13: Michael Richard Klugerman , Frank Thomson Leighton, Small-depth counting networks and related topics, Massachusetts Institute of Technology, 1994
• 14: Michael Klugerman , C. Greg Plaxton, Small-depth counting networks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.417-428, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129752]
• 15: C. P. Kruskal , M. Snir, A Unified theory of interconnection network structure, Theoretical Computer Science, v.48 n.1, p.75-94, Dec., 1986

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Theory

Keywords:
randomization, smoothing networks