AbstractBroadcasting 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.