The connectivity of hierarchical Cayley digraphs

The design and analysis of fault tolerant message routing schemes for large parallel systems has been the focus of much recent research. In this paper, the authors present a framework for the analysis of routing schemes in distributed memory multiprocessor systems containing faulty or unusable components. They introduce techniques for the derivation of the probabilities of successfully routing a single message using minimal path routing schemes. Using this framework, the authors derive closed form solutions for a wide range of routing schemes on the hypercube and on the two-dimensional mesh. The results obtained show the surprising resilience of the hypercube to a potentially large number of faults while demonstrating the inability of the mesh to tolerate a comparatively smaller number of faults.