Waking up an anonymous faulty network from a single source

Considers anonymous complete networks whose links and nodes are subject to random independent failures with fixed probabilities p<1 and q<1 respectively. A single fault-free node has to wake up all fault-free nodes by propagating a wakeup message through the network. In a unit of time, each node can communicate with at most one other node. Communications with a faulty node or via a faulty link do not succeed. For any /spl epsiv/>0, we present a wakeup algorithm for n-node networks, running in expected time O(log n) using an expected number O(n log n) message bits and working correctly with probability exceeding l/spl minus/n/sup /spl minusspl epsiv, for sufficiently large n. It is proved that these orders of magnitude are optimal.<>