Efficient schemes for massively fault-tolerant parallel communication.

This thesis examines the problems of designing massively fault-tolerant routing schemes and analyzing their performance. We concentrate primarily on distributed memory systems consisting of a large number of processors. The size of these parallel systems induces us to focus on distributed routing algorithms which require only local fault information, such as the fault status of immediate neighbors. Our notion of faults is quite general. We consider a processor (or communication link) to be faulty if it is unavailable for use in message communications. This definition includes hardware failures as well as congested processors (i.e., communications hot spots). Hence, it is quite natural for us to consider systems in which massive numbers of components are faulty. This thesis contains two main contributions. Our first contribution is the presentation of a set of techniques for deriving closed form solutions for the probability of successfully routing a single message using a minimal length path. We apply these techniques and derive solutions which allow us to compare the efficiency of different routing schemes. Our second contribution is the introduction of sidetracking, a technique used to design massively fault-tolerant parallel routing schemes. In a sidetracking scheme, if a message can not be routed in a forward direction, then it is routed to a randomly chosen non-forward neighbor. We demonstrate that sidetracking schemes achieve high performance, with low overhead, on a variety of parallel architectures and for a wide range of communication problems. Other researchers have studied the problem of developing massively fault-tolerant routing algorithms. In general, their papers have built on the fundamental work of Valiant, extending his paradigm to produce performance bounds for full permutation routing. In order to be able to provide these analytic bounds, the routing methods used are quite involved. We choose to attack the problem in a different manner, by showing that a simple technique, requiring only simple assumptions, produces routing schemes which achieve high performance in a wide range of applications. The performance bounds we obtain provide useful lower bounds for the performance of more complicated schemes.PhDComputer Science and EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/103528/1/9034426.pdfDescription of 9034426.pdf : Restricted to UM users only