@inproceedings{c797256c6c9742e6b176063445718cdc,
title = "Waking up an anonymous faulty network from a single source",
abstract = "We consider 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 ε>0 we present a wakeup algorithm for n-node networks, running in expected time O(log n), using an expected number of O(n log n) message bits and working correctly with probability exceeding 1-n-ε, for sufficiently large n. It is proved that these orders of magnitude are optimal.",
author = "Chlebus, {Bogdan S.} and Krzysztof Diks and Andrzej Pelc",
year = "1994",
month = jan,
day = "1",
language = "English (US)",
isbn = "0818650605",
series = "Proceedings of the Hawaii International Conference on System Sciences",
publisher = "Publ by IEEE",
pages = "187--193",
editor = "Nunamaker, {Jay F.} and Sprague, {Ralph H.Jr.}",
booktitle = "Proceedings of the Hawaii International Conference on System Sciences",
note = "Proceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5) ; Conference date: 04-01-1994 Through 07-01-1994",
}