This paper considers fault-tolerance on the R-Mesh and LR-Mesh models. We propose a technique to identify a healthy sub-mesh from a faulty model using the removal fault model. Then, we use scalable algorithms to simulate the faulty model on the resulting healthy sub-mesh. We also extend this work to cover more restrictive variations of the reconfigurable mesh, specifically, the NXR-Mesh and NXLR-Mesh. The overhead for the R-Mesh and NXR-Mesh is O(log n), and we obtain a constant overhead for the LR-Mesh and NXLR-Mesh.