The Wakeup Problem
- 1 December 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 25 (6) , 1332-1357
- https://doi.org/10.1137/s0097539793254959
Abstract
We study a new problem---the wakeup problem---that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, and other related problems. The main question we try to answer is ``How much memory is needed to solve the wakeup problem?'' We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.Keywords
This publication has 42 references indexed in Scilit:
- An O(n log n) unidirectional distributed algorithm for extrema finding in a circlePublished by Elsevier ,2004
- Self-stabilization of dynamic systems assuming only read/write atomicityDistributed Computing, 1993
- Token systems that self-stabilizeIEEE Transactions on Computers, 1989
- Linda in contextCommunications of the ACM, 1989
- Uniform self-stabilizing ringsACM Transactions on Programming Languages and Systems, 1989
- On the minimal synchronism needed for distributed consensusJournal of the ACM, 1987
- How processes learnDistributed Computing, 1986
- A belated proof of self-stabilizationDistributed Computing, 1986
- An improved algorithm for decentralized extrema-finding in circular configurations of processesCommunications of the ACM, 1979
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974