Oblivious deadlock-free routing in a faulty hypercube

摘要

A central problem in massively parallel computing is efficientlyrouting data between processors. This problem is complicated by twoconsiderations. First, in any massively parallel system, some processorsare bound to fail, disrupting message routing. Second, one must avoiddeadlock configurations in which messages permanently block one another.We present an efficient, oblivious, and deadlock-free routing algorithmfor the hypercube. The algorithm tolerates a large number of faults in aworst-case configuration