Time-relaxed 1-fault tolerant broadcast networks

Brian Q. Rieksts, Jose A. Ventura

Research output: Contribution to journalArticlepeer-review


In a 1-fault tolerant minimal broadcast network, a node of a network, called the originator, has a message which is to be transmitted to all other nodes of the network in minimum time regardless of the failure of a single communication line. In some instances, it is advantageous to use time-relaxed broadcast networks that require slightly more than the minimum transmission time, but have sparser edge sets. This paper presents a general compounding algorithm to construct sparse, time-relaxed, 1-fault tolerant broadcast networks. In the algorithm, copies of a broadcast network without faults are interconnected with additional edges according to the structure of a 1-fault tolerant broadcast network with two special properties. Both the 1-fault tolerant broadcast network and the broadcast network without faults may be time-relaxed. Computational results show that the algorithm yields sparser networks by allowing additional time units.

Original languageEnglish (US)
Pages (from-to)335-353
Number of pages19
JournalParallel Processing Letters
Issue number2
StatePublished - Jun 2009

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Time-relaxed 1-fault tolerant broadcast networks'. Together they form a unique fingerprint.

Cite this