Computing with faulty arrays

ABSTRACT

We present and O(1) slowdown emulation of a fault-free N x N two dimensional mesh with a slack of O(log N log log N) by a faulty mesh of the same size and slack. All components of the faulty mesh, including the memory modules, are assumed to be subject to failure. The faults may occur at any time during the emulation and the system readjusts dynamically.

REFERENCES

• ABO91: Yonatan Aumann , Michael Ben-Or, Asymptotically optimal PRAM emulation on faulty hypercubes (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.440-446, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185404]
• Gri89: G. Grimmet. Percolation. Springer- Verlag, 1989.
• KKL+90: C. Kaklamanis, A.R. Karlin, F.T. Leighton, V. Milenkovoc, P. Raghavan, S. Roa, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proceedings of the 31st Annual Symposium on the Foundations of Computer Science, pages 285-296, 1990.
• KLM+89: R. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73029]
• KPRS91: Z. M. Kedem , K. V. Palem , A. Raghunathan , P. G. Spirakis, Combining tentative and definite executions for very fast dependable parallel computing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.381-390, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103459]
• KPS90: Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100231]
• KS89: P. C. Kanellakis , A. A. Shvartsman, Efficient parallel algorithms can be made robust, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.211-219, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72996]
• MSP90: C. Martel, R. Subramonian, and A. Park. Asynchronous PRAMs are (almost) as good as synchronous PRAMs. In Proceedings of the 31th Annual Symposium on the Foundations of Computer Science, pages 590-599, 1990.
• Rab89: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• Rag89: P. Raghavan, Robust algorithms for packet routing in a mesh, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.344-350, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72972]
• Val90: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

General Terms:
Algorithms, Performance, Theory