More Web Proxy on the site http://driver.im/

article

Breaking the Θ(nlog2n) Barrier for Sorting with Faults

Authors:

C.Greg PlaxtonAuthors Info & Claims

Journal of Computer and System Sciences, Volume 54, Issue 2

Pages 265 - 304

https://doi.org/10.1006/jcss.1997.1470

Published: 01 April 1997 Publication History

Abstract

In this paper, we study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most part, we focus on fault patterns that are random, i.e., where the result of each comparison is independently faulty with probability upper bounded by some constant. All previous fault-tolerant sorting circuits, networks, and parallel algorithms require (log2n) depth and/or (nlog2n) comparisons to sort n items. In this paper, we construct: a passive-fault-tolerant sorting circuit withO(nlognloglogn) comparators, thereby answering a question posed by Yao and Yao in 1985, a reversal-fault-tolerant sorting network withO(nloglog23n) comparators, thereby answering a question posed by Assaf and Upfal in 1990, and a deterministicO(logn)-stepO(n)-processor EREW PRAM fault-tolerant sorting algorithm, thereby answering a question posed by Feige, Peleg, Raghavan, and Upfal in 1990. The results are based on a new analysis of the AKS circuit, which uses a much weaker notion of expansion that can be preserved in the presence of faults. Previously, the AKS circuit was not believed to be fault-tolerant because the expansion properties that were believed to be crucial for the performance of the circuit are destroyed by random faults. Extensions of our results for worst-case faults are also presented.

References

[1]

M. Ajtai, J. Komlós, E. Szemerédi, Sorting in clog n parallel steps, Combinatorica, 3 (1983) 1-19.

Digital Library

[2]

1983, Proceedings, of the 15th Annual ACM Symposium on the Theory of Computing, May 1983

[3]

V.E. Alekseyev, Sorting algorithms with minimum memory, Kibernetika, 5 (1969) 99-103.

[4]

N. Alon, J.H. Spencer, Wiley¿ Interscience, New York, 1991.

[5]

S. Assaf, E. Upfal, 1990, Fault-tolerant sorting network, Proceedings, 31st Annual IEEE Symposium on Foundations of Computer Science, October 1990

Digital Library

[6]

K. E. Batcher, 1968, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference, 32

[7]

P. Donejko, K. Diks, A. Pelc, M. Piotrów, Reliable minimum finding comparator networks, Springer-Verlag, New York, 1994.

[8]

U. Feige, D. Peleg, P. Raghavan, E. Upfal, 1990, Computing with unreliable information, Proceedings, 22nd Annual ACM Symposium on the Theory of Computing, May 1990

Digital Library

[9]

D. Kleitman, T. Leighton, Y. Ma, 1994, On the design of Boolean circuits that contain partially unreliable gates, Proceeding, 35th Annual IEEE Symposium on Foundations of Computer Science, November 1994

Digital Library

[10]

D.E. Knuth, Addison¿Wesley, Reading, 1973.

[11]

T. Leighton, Morgan-Kaufmann, San Mateo, 1992.

[12]

T. Leighton, Y. Ma, 1993, Breaking the¿n2n, Proceedings, 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993

[13]

T. Leighton, Y. Ma, 1993, Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults, Proceedings, 5th Annual ACM Symposium on Parallel Algorithms and Architectures, July 1993

Digital Library

[14]

T. Leighton, Y. Ma, C. G. Plaxton, 1991, Highly fault-tolerant sorting circuits, Proceedings, 32nd Annual IEEE Symposium on Foundations of Computer Science, October 1991

Digital Library

[15]

T. Leighton, B. Maggs, 1990, Expanders might be practical: Fast algorithms for routing around faults in multibutterflies, Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science, October 1990

[16]

A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica, 8 (1988) 261-277.

[17]

M.S. Paterson, Improved sorting networks withON, Algorithmica, 5 (1990) 75-92.

[18]

N. Pippenger, 1985, On networks of noisy gates, Proceedings, 26th Annual IEEE Symposium on Foundations of Computer Science, October 1985

Digital Library

[19]

L. Rudolph, A robust sorting network, IEEE Trans. Comput., 34 (1985) 344-354.

[20]

M. Schimmler, C. Starke, A correction network forN, SIAM J. Comput., 18 (1989) 1179-1187.

Digital Library

[21]

A.C. Yao, F.F. Yao, On fault-tolerant networks for sorting, SIAM J. Comput., 14 (1985) 120-128.

Cited By

Goodrich MJacob RAgrawal KShun J(2023)Optimal Parallel Sorting with Comparison ErrorsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591093(355-365)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591093
Goodrich MOzel E(2023)External-Memory Sorting with Comparison ErrorsAlgorithms and Data Structures10.1007/978-3-031-38906-1_32(493-506)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-38906-1_32
Mahmud SHaque SChoudhury NOgden CGamess E(2022)Improving counting sort algorithm via data localityProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3520203(211-214)Online publication date: 18-Apr-2022
https://dl.acm.org/doi/10.1145/3476883.3520203
Show More Cited By

Index Terms

Breaking the Θ(nlog2n) Barrier for Sorting with Faults

Recommendations

Breaking the /spl Theta/(nlog/sup 2/ n) barrier for sorting with faults
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

We study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most part, we focus on fault patterns that are random, e.g., where the result of each comparison is independently faulty with ...
Sorting in Linear Time?

We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0 2w 1 inO(nloglogn) time for arbitraryw logn, a significant improvement over the bound ofO(nlogn) achieved by the fusion trees of Fredman and Willard. Provided thatw ...
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in $O(n)$ time, while it requires $O(n\log n)$-bit working space, where $n$ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 54, Issue 2

Special issue: papers from the 32nd and 34th annual symposia on foundations of computer science, Oct. 2–4, 1991 and Nov. 3–5, 1993

April 1997

166 pages

ISSN:0022-0000

Editors:
E. K. Blum
Univ. of Southern California, Los Angeles
,
Michael Sipser

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 1997

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Goodrich MJacob RAgrawal KShun J(2023)Optimal Parallel Sorting with Comparison ErrorsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591093(355-365)Online publication date: 17-Jun-2023
Goodrich MOzel E(2023)External-Memory Sorting with Comparison ErrorsAlgorithms and Data Structures10.1007/978-3-031-38906-1_32(493-506)Online publication date: 31-Jul-2023
Mahmud SHaque SChoudhury NOgden CGamess E(2022)Improving counting sort algorithm via data localityProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3520203(211-214)Online publication date: 18-Apr-2022
Abdel-Hafeez SGordon-Ross A(2017)An Efficient O( $N$ ) Comparison-Free Sorting AlgorithmIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2017.266174625:6(1930-1942)Online publication date: 22-May-2017
Caminiti SFinocchi IFusco ESilvestri F(2017)Resilient Dynamic ProgrammingAlgorithmica10.1007/s00453-015-0073-z77:2(389-425)Online publication date: 1-Feb-2017
Groz BMilo TMilo TCalvanese D(2015)Skyline Queries with Noisy ComparisonsProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745775(185-198)Online publication date: 20-May-2015
Milo TCalvanese D(2015)Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsundefinedOnline publication date: 20-May-2015
Hadjicostas PLakshmanan K(2011)Recursive merge sort with erroneous comparisonsDiscrete Applied Mathematics10.1016/j.dam.2011.05.010159:14(1398-1417)Online publication date: 1-Aug-2011
Ferraro-Petrillo UFinocchi IItaliano G(2010)Experimental study of resilient algorithms and data structuresProceedings of the 9th international conference on Experimental Algorithms10.1007/978-3-642-13193-6_1(1-12)Online publication date: 20-May-2010
Italiano G(2010)Resilient algorithms and data structuresProceedings of the 7th international conference on Algorithms and Complexity10.1007/978-3-642-13073-1_3(13-24)Online publication date: 26-May-2010
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents