DISTRIBUTED ALGORITHMS FOR GLOBAL STRUCTURING.

In order to fully utilize the speed and power inherent in a computer network, emphasis must be placed on the development of parallel (as opposed to sequential) algorithms. This paper investigates concurrent algorithms designed to impose a logical structure on top of the physical computer network, such as a pairing of the processors along communication lines. These algorithms are interesting not only for their relationship to parallel algorithms in general, but also because the resulting structure may be used as a basis for writing other parallel algorithms. The algorithms discussed form three types of structures on the network. These three problems have been chosen because their results are dependent upon the physical network configuration and because they apply to the solution of other network problems. Pairing algorithms match each node of the network with a direct neighbor. Spanning tree algorithms impose a tree on the network so that a unique path exists between any two processors in the network. The last problem considered is that of forming hierarchies of processors. One step in developing a hierarchy is the formation of processor cliques. Each clique should be of a certain size and one processor in each clique is designated as the ″leader.″ A good solution should try to minimize the average radius of each clique.