An O(nlogn)-size fault-tolerant sorting network (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(nlogn)-size fault-tolerant sorting network (extended abstract)

Full text

Pdf (1.05 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 266 - 275

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Yuan Ma

Department of Computer Science, Stanford University, Stanford, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 13, 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/237814.237876 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 31st 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 AFIP$ Spring Joint Computer Conference, volume 32, pages 307-314, 1968.
	4	Piotr Denejko , Krzysztof Diks , Andrzej Pelc , Marek Piotrów, Reliable Minimum Finding Comparator Networks, Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994, p.306-315, August 22-26, 1994
	5	U. Feige , D. Peleg , P. Raghavan , E. Upfal, Computing with unreliable information, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.128-137, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100230]
	6	R. L. Rivest , A. R. Meyer , D. J. Kleitman, Coping with errors in binary search procedures (Preliminary Report), Proceedings of the tenth annual ACM symposium on Theory of computing, p.227-232, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804351]
	7	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
	8	S.-Y. Kuo and S.-C. Liang. Defect-tolerant hierarchical sorting networks for wafer-scale integration. IEEE Journal of Solid-State Circuits, 26(9):1212-1222, 1991.
	9	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]
	10	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	11	Tom Leighton , Yuan Ma , C. Greg Plaxton, Breaking the &thgr;(nlog2n) barrier for sorting with faults, Journal of Computer and System Sciences, v.54 n.2, p.265-304, April 1997 [doi>10.1006/jcss.1997.1470]
	12	Tom Leighton , Yuan Ma, Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.30-41, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165235]
	13	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]
	14	Yuan Ma, Fault-tolerant sorting networks, Massachusetts Institute of Technology, Cambridge, MA, 1995
	15	M. S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5:75-92, 1990.
	16	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
	17	Nicholas Pippenger, Communication networks, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	18	C. Greg Plaxton, A hypercubic sorting network with nearly logarithmic depth, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.405-416, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129751]
	19	L. Rudolph. A robust sorting network. IEEE Transactions on Computers, 34:344-354, 1985.
	20	M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989 [doi>10.1109/12.21149]
	21	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]
	22	J. Sun, E. Cerny, and J. Gecsei. Design of a faulttolerant sorting network. In Proceedings of the Canadian Conference on Very Large Scale Integration, pages 235-242, October 1989.
	23	J. Sun, E. Cerny, and J. Gecsei. Sorting networks without critical stages. In Proceedings of the Canadian Conference on Very Large Scale Integration, pages 5.4/1-8, October 1990.
	24	Jianli Sun , E. Cerny , J. Gecsei, Fault Tolerance in a Class of Sorting Networks, IEEE Transactions on Computers, v.43 n.7, p.827-837, July 1994 [doi>10.1109/12.293261]
	25	J. Sun and J. Gecsei. A multiple-fault tolerant sorting network. In Proceedings of the 21st International Symposium on Fault-Tolerant Computing, pages 274-281, June 1991.
	26	J. Sun, J. Gecsei, and E. Cerny. An improvement in robust sorting networks. In Proceedings of the Twenty-Third A$ILOMAR Conference on Signals, Systems and Computers, volume 2, pages 1036-1040, October 1989.
	27	J. Sun , J. Gecsei , E. Cerny, Fault-tolerance in balanced sorting networks, Journal of Electronic Testing: Theory and Applications, v.1 n.1, p.31-41, Feb. 1990 [doi>10.1007/BF00134013]
	28	A. C. Yao and F. F. Yao. On fault-tolerant networks for sorting. SIAM J. Comput., 14:120-128, 1985.

CITED BY 3

	Bruce M. Maggs , Berthold Vöcking, Improved routing and sorting on multibutterflies, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.517-530, May 04-06, 1997, El Paso, Texas, United States
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	Marek Piotrów, Periodic, random-fault-tolerant correction networks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.298-305, July 2001, Crete Island, Greece