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

Article

Periodic, random-fault-tolerant correction networks

Author:

Marek PiotrówAuthors Info & Claims

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

Pages 298 - 305

https://doi.org/10.1145/378580.378697

Published: 03 July 2001 Publication History

Abstract

We study the problem of sorting sequences of N-keys that can be obtained from sorted ones by changing values of s, 0 < s ⪇ N, keys at unknown positions. Such s-disturbed sequences can appear as outputs of a sorting network that contains faulty comparators. We present a simple comparator network of depth 4 that sorts 1-disturbed sequences in logarithmic time, where the network is used repeatedly, i.e. if its output is not sorted, the network is run again taking the output as input. Then we analyze the passive-fault model of comparator networks introduced by Yao and Yao, where a faulty comparator outputs directly its input without making a comparison. In this context, we give a construction of N-input, f-fault-tolerant comparator networks of depth 6 that sort 1-disturbed sequences in time Ο(logN + f). Finally, we prove that choosing f = Ο(logN) one can make such networks random-fault-tolerant. In the last two results the constructions and their analysis are simpler as the previous non-periodic ones, and still their runtimes are asymptotically optimal.

References

[1]

M. Ajtai, J. Komlos and E. Szemeredi, An O(nlog n) sorting network, in Proc. 15th Annual ACM Symp. on Theory of Computing, 1983, pp. 1-9.]]

Digital Library

[2]

K.E. Batcher, Sorting networks and their applications, in Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, NJ, pp. 307-314.]]

[3]

M. Dowd, Y. Perl, M. Saks and L. Rudolph, The periodic balanced sorting network, Journal of ACM, 36 (1989), pp. 738-757.]]

Digital Library

[4]

R. Diekmann, J. Gehring, R. L~ling, B. Monien, M. N~bel and R. Wanka, Sorting Large Data Sets on a Massively Parallel System, in Proc. 6th IEEE-SPDP, 1994, pp. 2-9.]]

Digital Library

[5]

D.E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison Wesley, Reading, MA, 1975.]]

Digital Library

[6]

M. Kik, Periodic Correction Networks, in Proc. 6th International Euro-Par Conference, Lect. Notes Comp. Sci., Vol. 1900, Springer-Verlag, Berlin 2000, pp. 471-478.]]

Digital Library

[7]

M. Kik, M. Kutyowski and M. Piotr~w, Correction Networks, in Proc. 1999 International Conference on Parallel Processing, IEEE Computer Society, California 1999, pp. 40-47.]]

Digital Library

[8]

M. Kutyowski, K. Lory's and B. Oesterdiekhoff, Periodic Merging Networks, Theory of Computing Systems, 31.5 (1998), pp. 551-578.]]

[9]

M. Kutylowski, K. Lory's, B. Oesterdiekhoff and R. Wanka, Fast and feasible periodic sorting networks of constant depth, in Proc. 35th Annual IEEE Symp. on Foundations of Computer Science, 1994, pp. 369-380.]]

Digital Library

[10]

F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercubes, Morgan-Kaufmann, San Mateo, CA, 1992.]]

Digital Library

[11]

F.T. Leighton, Y. Ma and C.G. Plaxton, Breaking the T (nlog 2 n) barrier for sorting with faults, J. Comput. System Sci., 54 (1997), pp. 265-304. The preliminary version, by F.T. Leighton and Y. Ma, appeared in Proc. 34th Annual IEEE Symp. on Foundations of Computer Science, 1993, pp. 734-743.]]

Digital Library

[12]

Y. Ma, An O(nlog n)-size fault-tolerant sorting network, in Proc. 26th Annual ACM Symp. on the Theory of Computing 1996, pp. 266-275.]]

Digital Library

[13]

M. Piotr~w, Optimal sorting networks resistant to k passive faults, in Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 242-251.]]

Digital Library

[14]

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.]]

Digital Library

[15]

M. Schimmler and C. Starke, A correction network for N-sorters, SIAM J. Computing 18 (1989), pp. 1179-1187.]]

Digital Library

[16]

G. Stachowiak, Fibonacci correction networks, in Proc. 7th Scandinavian Workshop on Algorithms Theory, Lect. Notes Comp. Sci., Vol. 1851, Springer-Verlag, Berlin 2000, pp. 535-548.]]

Digital Library

[17]

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

Cited By

Stachowiak G(2019)Fast periodic correction networksTheoretical Computer Science10.1016/j.tcs.2005.11.031354:3(354-366)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2005.11.031
Piotrów M(2019)A note on constructing binary heaps with periodic networksInformation Processing Letters10.1016/S0020-0190(01)00320-983:3(129-134)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/S0020-0190%2801%2900320-9
Piotrów M(2016)Faster merging networks with a small constant periodTheoretical Computer Science10.1016/j.tcs.2016.05.038640:C(20-40)Online publication date: 9-Aug-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.038
Show More Cited By

Index Terms

Periodic, random-fault-tolerant correction networks

Recommendations

Depth Optimal Sorting Networks Resistant to k Passive Faults

We study the problem of constructing a sorting network that is tolerant to faults and whose running time (i.e., depth) is as small as possible. We consider the scenario of worst-case comparator faults and follow the model of passive comparator failure ...
Fault Tolerance in a Class of Sorting Networks

The early study of fault tolerance in efficient sorting networks only achieved single-fault tolerance. By eliminating critical comparators, L. Rudolph (1985) presented a 1-fault tolerant design of the balanced sorting network (BSN) at the cost of one ...
Optimal-depth sorting networks

We prove depth optimality of sorting networks from "The Art of Computer Programming".Sorting networks posses symmetry that can be used to generate a few representatives.These representatives can be efficiently encoded using regular expressions.We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

July 2001

340 pages

ISBN:1581134096

DOI:10.1145/378580

Chairman:
Arnold Rosenberg
Univ. of Massachusetts

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA01

Sponsor:

SPAA01: 13th ACM Symposium on Parallel Algorithms and Architectures

Crete Island, Greece

Acceptance Rates

SPAA '01 Paper Acceptance Rate 34 of 93 submissions, 37%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
232
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stachowiak G(2019)Fast periodic correction networksTheoretical Computer Science10.1016/j.tcs.2005.11.031354:3(354-366)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2005.11.031
Piotrów M(2019)A note on constructing binary heaps with periodic networksInformation Processing Letters10.1016/S0020-0190(01)00320-983:3(129-134)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/S0020-0190%2801%2900320-9
Piotrów M(2016)Faster merging networks with a small constant periodTheoretical Computer Science10.1016/j.tcs.2016.05.038640:C(20-40)Online publication date: 9-Aug-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.038
Piotrów MBlelloch GSanders P(2014)Faster 3-periodic merging networksProceedings of the 26th ACM symposium on Parallelism in algorithms and architectures10.1145/2612669.2612700(223-225)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1145/2612669.2612700

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents