Derivation of a Distributed Implementation of Warshall's Algorithm

摘要

A distributed implementation of an algorithm for computing the transitive closure of a binary relation is derived. The boolean matrix is distributed over a network of cells. Execution of one phase of the algorithm is made possible by routing the matrix elements involved through the network. The proof obligation to avoid multiple messages on a connection leads to the timing of successive phases. The resulting program is very similar to, although an order of magnitude shorter than, the cellular automaton described in Scoy (1980) and very different from the systolic array described in Guidas et al (1979).