Percolation theory and computing with faulty arrays of processors

ABSTRACT

Let H be an n x n mesh-connected array of processors. Each processor is assumed to fail (independently) with probability p. Raghavan [5] gave an algorithm that with high probability routes packets in this mesh with O(log n) dilation and O(log2n) load so long as p ≤ 0.29. KKLMRRTT [3] improve the load to O(1) for “small” p while keeping the O(log n) bound for dilation and showing an o(1) bound for congestion. In this paper we show these bounds hold for p as high as *** 0.4. We also consider the problem where links rather than processors fail and shows these same bounds hold for q < 1/2. In both cases these bounds are tight: for greater probabilities of failure the above embedding bounds cannot be achieved. This short cutoff follows from a zero-one result of percolation theory.

REFERENCES

• 1: M. Aizenman, J. T. Chayes, L. Chayes, J. Fr5hlich, and L. Russo. On a sharp transition kom area law to perimeter law in a system of random surfaces. Communications in Mathematical Physics, 92:19-69, 1983.
• 2: Geoffrey Grimmett. Percolation. Springer-Verlag, 1989.
• 3: C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, and A. Tsantila~. Asymptotically tight bounds for computing with faulty arrays of processors. In Twenty Second Ann~tol Syrup. on Theory of Computing, pages 285-296, 1990.
• 4: H. Kesten. The critical probability of bond percolation on the square lattice equals 7' Communications in Mathematical Physzcs, 71:41-59, 1980.
• 5: 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]
• 6: L. Russo. On the critical percolation probabilities. Zeitschrift fi~'r l,~a. hrscheinlichkeitstheorie und Verwandte Gebiete, 56:229-237, 1981.
• 7: D. Stauffer. Introd~tction to Percolation Theory. Taylor and Francis, 1985.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory, Verification