Periodic, random-fault-tolerant correction networks
Marek Piotrów · 2001
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.