The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
Randomized Consensus in Expected $O(N\log^2N)$ Operations Per Processor
James Aspnes, Orli Waarts,
Pages. 1024-1044
Abstract
Contents 1. Introduction
2. Intuition and relation to previous results
3. The shared-coin protocol
4. Martingales
4.1. Knowledge, $\sigma$-algebras, and measurbility
4.2. Definition of a martingale
4.3. Gambling systems
4.4. Limit theorems
5. Proof of correctness
5.1. Phases of the protocol
5.2. Common votes
5.3. Extra votes
5.4. Written votes vs. decided votes
5.5. Choice of parameters
6. Discussion
Key words consensus, distributed algorithms, shared memory, randomized algorithms, asyn-chronous computation, martingales.
Mathmatical Subject Classification 68Q22, 60G42, 60F10