Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults

Full text

Pdf (1.09 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 30 - 41

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Tom Leighton	Massachusetts Institute of Technology, Cambridge
Yuan Ma	Massachusetts Institute of Technology, Cambridge

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 3

Additional Information:

references cited by 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/165231.165235 What is a DOI?

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	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]
	2	S. Assaf and E. Upfal. Fault-tolerant sorting network. In Proceedings of the 32st Annual IEEE Symposium on Foundations of Computer Science, pages 275-284, October 1990.
	3	K. E. Batcher. Sorting networks and their applications. In Proceedings of the A FIPS Spring Joint Computer Conference, volume 32, pages 307-314, 1968.
	4	R. Ehrenborg, D. Kleitman, T. Leighton, and Y. Ma. A new type of fault-tolerant Boolean circuit. In preparation, 1993.
	5	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	6	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	7	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	8	T. Leighton and Y. Ma. Beating the Q(n log2 n) barrier for fault-tolerant sorting. In preparation, 1993.
	9	Tom Leighton , Yuan Ma , C. Greg Plaxton, Highly fault-tolerant sorting circuits, Proceedings of the 32nd annual symposium on Foundations of computer science, p.458-469, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185406]
	10	N. Pippenger. On networks of noisy gates. In Proceedings of the 26st Annual IEEE Symposium on Foundations of Computer Science, pages 30-36, October 1985.
	11	L. Rudolph. A robust sorting network. IEEE Transactions on Computers, 34:344- 354, 1985.
	12	M. Schimmler , C. Starke, A correction network for N-sorters, SIAM Journal on Computing, v.18 n.6, p.1179-1187, Dec. 1989 [doi>10.1137/0218078]
	13	A. C. Ya, o #nd F. F. Y#o. On f#ult-tolerant networks for sorting. SIAM J. Comput., 14:120-128, 1985.

CITED BY 3

	Yuan Ma, An O(nlogn)-size fault-tolerant sorting network (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.266-275, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Marek Piotrów, Depth optimal sorting networks resistant to k passive faults, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.242-251, January 28-30, 1996, Atlanta, Georgia, United States
	Nabil Kahale , Tom Leighton , Yuan Ma , C. Greg Plaxton , Torsten Suel , Endre Szemerédi, Lower bounds for sorting networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.437-446, May 29-June 01, 1995, Las Vegas, Nevada, United States