2.5n-step sorting on n×n meshes in the presence of o(√n) worst-case faults

In this paper we propose the robust algorithm-configured emulation (RACE) scheme for the design of simple and efficient robust algorithms that can run on faulty mesh-connected computers. We show that 1-1 sorting (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 mesh with an arbitrary pattern of o(√n) faults. This running time has exactly the same leading constant as the best known algorithms for 1-1 sorting on an n×n fault-free mesh. We also formulate the mesh robustness theorem, which leads to a variety of efficient robust algorithms on faulty meshes