Accession Number : ADA192929

Title :   Distributed Fault Tolerant Embeddings of Binary Trees in Hypercubes.

Descriptive Note : Technical rept.,

Corporate Author : PITTSBURGH UNIV PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Provost, Foster ; Melhem, Rami

PDF Url : ADA192929

Report Date : Jan 1988

Pagination or Media Count : 26

Abstract : This paper presents a distributed algorithm for embedding binary trees in hypercubes. Starting with the root (invoked in some cube node by a host), each node is responsible for determining the addresses of its children, and for invoking the embedding algorithm for the subtree rooted at each child in the proper cube node. This distributed embedding, along with the wealth of communication links in the hypercube, leads to a high potential for fault tolerance. We demonstrate the fault tolerance capability by introducing tree restructuring techniques which may be used to tolerate faults during the initial embedding, as well as to remap nodes that fail at run-time. The distributed nature of the embedding eliminates the need for global knowledge of faulty nodes; each node must only know the status of its neighbors.

Descriptors :   *EMBEDDING, *FAULT TOLERANT COMPUTING, ALGORITHMS, COMMUNICATIONS NETWORKS, DISTRIBUTION, TOPOLOGY

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE