A randomized, o(log w)-depth 2 smoothing network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A randomized, o(log w)-depth 2 smoothing network

Full text

Pdf (460 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures table of contents

Calgary, AB, Canada

SESSION: Network organization and design table of contents

Pages 178-187

Year of Publication: 2009

ISBN:978-1-60558-606-9

Authors

Marios Mavronicolas	University of Cyprus, Nicosia, Cyprus
Thomas Sauerwald	International Computer Science Institute (ICSI), Berkeley, CA, USA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 18, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1583991.1584043 What is a DOI?

ABSTRACT

A K-smoothing network is a distributed, low-contention data structure where tokens arrive arbitrarily on w input wires and reach w output wires via their completely asynchronous propagation through the network. The maximum discrepancy among the numbers of tokens arriving at the ouput wires, called smoothness, is at most K. It has been a long-standing open problem to construct a K-smoothing network with (i) optimal K, (ii) optimal Θ(log w) depth (called small-depth), (iii) no use of the AKS sorting network, and (iv) no reliance on global initialization.

In this work, we present a very simple, randomized network which meets all four desiderata:

• It is the cascade of a reasonably small number (about 150) of copies of the simple block network (Dowd et al., JACM'89); hence, it is small-depth and does not use the AKS sorting network.

• It achieves smoothness K = 2; hence, it is optimal with respect to smoothness due to a recent improbability result about randomized, small-depth, 1-smoothing networks (Mavronicolas and Sauerwald, PODC'08).

• The network is randomized: each balancer is oriented independently and uniformly at random, thus requiring no global initialization.

Cascaded before the Θ(log w)-depth 2-counter network due to Klugerman and Plaxton (STOC'92), which does use the AKS sorting network as a building block, our 2-smoothing network yields a new, randomized counting network with depth Θ(log w). The new network is a much simpler alternative to the classical, small-depth counting networks from Klugerman and Plaxton.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Eran Aharonson , Hagit Attiya, Counting networks with arbitrary fan-out, Distributed Computing, v.8 n.4, p.163-169, June 1995 [doi>10.1007/BF02242734]
	2	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]
	3	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]
	4	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]
	5	K. E. Batcher, Sorting networks and their applications, Proceedings of the April 30--May 2, 1968, spring joint computer conference, April 30-May 02, 1968, Atlantic City, New Jersey [doi>10.1145/1468075.1468121]
	6	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]
	7	Tobias Friedrich , Thomas Sauerwald, Near-perfect load balancing by randomized rounding, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536433]
	8	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]
	9	M. Herlihy and S. Tirthapura, "Self-Stabilizing Smoothing and Counting Networks," Distributed Computing, Vol. 18, No. 5, pp. 345--357, 2006.
	10	W. Hoeffding. "Probability Inequalities for Sums of Bounded Random Variables," Journal of the American Statistical Association, Vol. 53, No. 301, pp. 13--30, 1963.
	11	Distributed, Low Contention Task Allocation, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.358, October 23-26, 1996
	12	Michael Richard Klugerman , Frank Thomson Leighton, Small-depth counting networks and related topics, Massachusetts Institute of Technology, 1994
	13	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]
	14	Marios Mavronicolas , Thomas Sauerwald, The impact of randomization in smoothing networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400797]
	15	Shlomo Moran , Gadi Taubenfeld, A lower bound on wait-free counting, Journal of Algorithms, v.24 n.1, p.1-19, July 1997 [doi>10.1006/jagm.1996.0837]
	16	Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]