Nordic Journal of Computing Bibliography

B. S. Chlebus, K. Diks, and A. Pelc. Sparse networks supporting efficient reliable broadcasting. Nordic Journal of Computing, 1(3):332-345, Fall 1994.
Abstract

Broadcasting concerns transmitting information from a node of a communication network to all other nodes. We consider this problem assuming that links and nodes of the network fail independently with given probabilities p < 1 and q < 1, respectively. For a positive constant epsilon, broadcasting in an n-node network is said to be epsilon-safe, if source information is transmitted to all fault-free nodes with probability at least 1 - n-epsilon. For any p < 1, q < 1 and epsilon > 0 we show a class of n-node networks with maximum degree O(log n) and epsilon-safe broadcasting algorithms for such networks working in logarithmic time.


Shortcuts:

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