Competitive fault-tolerance in area-universal networks
Sivan Toledo · 1992
In this paper we study fault tolerance in area-universal networks and provide both positive and negative results. We present a new network layout, the mesh of ladders, which is area-universal and fault-tolerant. This network, laid out in an n n area, can simulate any other network layout laid out in the same area with O(log 4 n) slowdown, even if cn/2 log n blocks of size 2 log n 2 log n become faulty (for some constant c < 1). Furthermore, it can simulate any other network layout which has at most f(n) bends in each wire with slowdown O(f(n) log 2 n) even after any number of such blocks become faulty in both networks. Our results are tight, in the sense that if one of our assumptions is removed, it is no longer possible to obtain similar simulation results. We show for example that the width of a layout for a network with at least n nodes and diameter at most n 1-# for any fixed 1/2 < # < 1 must be at least # n). Therefore, if faults can happen in any pattern the remaining non...