Randomness and Robustness in Hypercube Computation

Abstract

In this thesis we explore means by which hypercubes can compute despite faulty processors and links. We also study techniques which enable hypercubes to simulate dynamically changing networks and data structures. In chapter two, we investigate strategies for routing permutations on faulty hypercubes. We assume that each node or edge in the hypercube fails with constant probability and that failures are independent of one another. We describe a routing algorithm which successfully routes messages between working processors in O(log N) steps on an N-node faulty hypercube with high probability.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1991
Accession Number
ADA261889

Entities

People

  • Mark J. Newman

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Classification
  • Computations
  • Computer Science
  • Computers
  • Fault Tolerance
  • Inequalities
  • Information Processing
  • Lepidoptera
  • Load Monitoring
  • Notation
  • Observation
  • Probability
  • Random Variables
  • Security
  • Simulations
  • Three Dimensional
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Fault Tolerant Diagnosis of Black and White Balloon Isolation Tests Using ¥.
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design