In this paper we propose the robust algorithm-configured emulation(RACE) scheme for the design of simple and efficient robust algorithmsthat can run on faulty mesh-connected computers. We show that 1-1sorting (1 key per healthy processor) can be performed in 2.5n+o(n)communication steps and 2n+o(n) comparison steps on an n×n meshwith an arbitrary pattern of o(√n) faults. This running time hasexactly the same leading constant as the best known algorithms for 1-1sorting on an n×n fault-free mesh. We also formulate the meshrobustness theorem, which leads to a variety of efficient robustalgorithms on faulty meshes
展开▼
