Lower Bounds on Correction Networks

摘要

Correction networks are comparator networks that sort inputs differing from sorted sequences of length N in a small number of positions. The main application of such networks is producing fault-tolerant sorting networks. We show the lower bound 1.44log2 N on the depth of correction networks settling an open problem from [7]. This bound is tight since the upper bound 1.44 Iog2 N is known.