Distributed Fault Tolerant Embeddings of Binary Trees in Hypercubes.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1988
Accession Number
ADA192929

Entities

People

  • Foster Provost
  • Rami Melhem

Organizations

  • University of Pittsburgh

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Detection
  • Distributed Computing
  • Embedding
  • Fault Tolerance
  • Short Circuits
  • Simulations
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Neural Network Machine Learning.
  • Parallel and Distributed Computing.