The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Average and Randomized Complexity of Distributed Problems
Nechama Allenberg-Navony, Alon Itai, Shlomo Moran,
Pages. 1254-1267
Abstract
Contents 1. Introduction
2. Preliminaries
2.1. Distributed systems
2.2. Distributed tasks
2.3. Average cost of deterministic algorithms
2.4. Randomized algorithms
2.5. Relationship to other models
3. Yao's lemma
3.1. Restating Yao's lemma
3.2. Main results
3.3. Randomized algorithms that are correct with probability 1.
4. Applications
5. Bounded error
6. An open problem
Key words distributed
Mathmatical Subject Classification 68Q22, 68Q25