Nordic Journal of Computing Bibliography

K. Diks and A. Pelc. Fault-Tolerant Linear Broadcasting. Nordic Journal of Computing, 3(2):188-201, Summer 1996.
Abstract

In linear broadcasting, packets originally stored in one node, called the source, have to visit all other nodes of the network. Every packet has a predetermined route indicating in which order it visits the nodes. A faulty link or node of the network destroys all packets passing through it. A linear broadcasting scheme consisting of packets' routes is f-fault-tolerant if every fault-free node is visited by at least one packet for any configuration of at most f link or node failures. We estimate the minimum number of packets for which there exists an f-fault-tolerant linear broadcasting scheme in complete networks, and we construct schemes using few packets. Variations of this problem when faults can occur only in links or only in nodes are also considered.

Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]; C.4 [Performance of Systems]; G.2.1 [Discrete Mathematics]: Combinatorics; G.4 [Mathematical Software]

Additional Key Words and Phrases: broadcasting, fault-tolerance, packet, route

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database