Deadlock-free message routing in multicomputer networks

The execution of a concurrent computation by a network of processors requires a routing algorithm that is deadlock free. Many routing algorithms proposed for processor networks have the potential of deadlock due to the cyclic topology of the network. In this paper we first formalize the concept of message routing. Next, we show a method by which a deadlock-free routing algorithm can be constructed out of a given routing algorithm. Finally the method is illustrated by constructing deadlock-free routing algorithms for cartesian product processor networks