Technical Report
 

Efficient fault tolerant broadcasting algorithm for the hypercube

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/technical_reports/76537831f

Descriptions

Attribute NameValues
Alternative Title
Creator
Abstract
  • One of the most popular topologies is the hypercube, that has n = 2ᵏ processors, numbered 0 to 2ᵏ -1 and connected in such a way that there is a link between any two if and only if they differ in one bit. Its popularity is due to the fact that a large number of processors can be interconnected using a small number of communication links while at the same time keeping the communication delay between processors at minimum. Broadcasting is a procedure by which a processor can pass a message to all other processors in the network non redundantly; it is extremely important for diagnosis of the network, distribution agreement or clock synchronization. In this paper we present some interesting features and properties of the hypercube and then we describe the algorithm for broadcasting in the hypercube, by Sullivan and Bashkow. Finally, we develop a simple yet efficient algorithm for broadcasting m the hypercube in the presence of some faulty processors.
Resource Type
Date Issued
Academic Affiliation
Series
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

Items