Robust algorithms for packet routing in a mesh

This paper considers the problem of permutation packet routing on a √n×√n mesh-connected array of processors. Each node in the array is assumed to be independently faulty with a probability bounded above by a value p. This paper gives a routing algorithm which, if p≤ 0.29, will with very high probability route every packet that can be routed in O(√n log n) steps with queue lengths that are O(log2n). Extensions to higher-dimensional meshes are given. © 1995 Springer-Verlag New York Inc.