Skip to search boxSkip to navigationSkip to main content

Waking up an anonymous faulty network from a single source

*Corresponding author for this work
  • 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

Conference

Date

01/04/1994 - 01/07/1994

Location

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 IEEE

Publication series

  • Publication series name: Proceedings of the Hawaii International Conference on System Sciences
    ISSN (Print): 1060-3425
    Volume: 2
0818650605

Publication IDs

  • Scopus: 0028014774

Host publication title

Proceedings of the Hawaii International Conference on System Sciences

Host publication editors

  • Jay F. Nunamaker
  • Ralph H.Jr. Sprague

Publication metrics

Metrics

Scopus
citations
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1

PlumX

Citation count
3