Waking up an anonymous faulty network from a single source
- Bogdan S. Chlebus(corresponding author),
- Krzysztof Diks,
- Andrzej Pelc
- University of Warsaw
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research
Related Event
Title
Proceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5)
Event type
ConferenceDate
01/04/1994 - 01/07/1994Location
Wailea, HI, USA
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.
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research
Original language
English (US)Pages from-to (Number of pages)
Pages 187-193 (7 pages)Publication milestones
- Published - 1994
Publication status
Published - 1994
Publisher
Publ by IEEEPublication series
- Publication series name: Proceedings of the Hawaii International Conference on System Sciences
ISSN (Print): 1060-3425
Volume: 2
ISBN (Print)
0818650605Publication IDs
- Scopus: 0028014774
Host publication title
Proceedings of the Hawaii International Conference on System SciencesHost publication editors
- Jay F. Nunamaker
- Ralph H.Jr. Sprague
Access to documents
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
PlumX
Citation count
3
