The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
The Wakeup Problem
Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld,
Pages. 1332-1357
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.
Contents 1. Introduction
1.1. The wakeup problem
1.2. A new model
1.3. Space-complexity results
1.4. Relation to other problems
2. Definitions and notations
2.1. Protocols and knowledge
2.2. Wakeup, consensus, and leader-election protocols
3. Fault-free solutions
4. Fault-tolerant solutions
5. A lower bound
5.1. Reachability graphs and terminal graphs
5.2. Reachability graphs
5.3. Main construction
5.4. Remarks
6. Relation to other problems
7. Conclusions
Key words fault tolerance, shared memory, concurrency, algorithms.
Mathmatical Subject Classification 68M99, 68Q10, 68Q25