Recursive data structures are a common feature of program design. Using them in a distributed system raises many problems. An existing solution uses a node-naming strategy to ensure that all the processors can refer to the nodes of the structure in an unambiguous way. Motivated by the problem of evaluating functions with commutative recursive function calls, I have extended the method to uniquely name the nodes that occur in the structures arising from these evaluations. The method also allows nested recursive structures, such as trees of lists to be described simply. The method has been proved correct, and implemented on the Cray T3D, along with a set of library functions that allow a user to manipulate recursive datatypes in a parallel environment.
Tim Lewis
