Networks of Machines for Distributed Recursive Computations

Abstract

Distributed computations may be viewed as a set of communicating processes. If such a computation is to be executed by a multi-processor system, the processes have to be distributed over the processors and the communications have to be distributed over a network. This leads to the questions of load balancing and message routing. In this paper we consider distributed recursive computations and we propose a class of processor networks that admits a homogeneous dist ribution of processes and trivial routing. Furthermore, we identify a subclass that admits a planar embedding of the network.