Randomized protocols for asynchronous consensus

被引：78
作者：
Aspnes, J [1 ]
机构：
[1] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
来源：
DISTRIBUTED COMPUTING | 2003年 / 16卷 / 2-3期
关键词：
consensus; agreement; randomization; asynchrony;
D O I：
10.1007/s00446-002-0081-5
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.
引用
收藏
页码：165 / 175
页数：11
相关论文
共 53 条
[1]  
Abrahamson K., 1988, Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, P291, DOI 10.1145/62546.62594
[2]   The power of multiobjects [J].
Afek, Y ;
Merritt, M ;
Taubenfeld, G .
INFORMATION AND COMPUTATION, 1999, 153 (01) :117-138
[3]   Computing with faulty shared objects [J].
Afek, Y ;
Greenberg, DS ;
Merrit, M ;
Taubenfeld, G .
JOURNAL OF THE ACM, 1995, 42 (06) :1231-1274
[4]   Failure detection and consensus in the crash-recovery model [J].
Aguilera, MK ;
Chen, W ;
Toueg, S .
DISTRIBUTED COMPUTING, 2000, 13 (02) :99-125
[5]  
Aguilera MK, 1999, SIAM J COMPUT, V28, P890, DOI 10.1137/S0097539796312915
[6]  
AGUILERA MK, 1998, TR981682 CORNELL U C
[7]   Time-adaptive algorithms for synchronization [J].
Alur, R ;
Attiya, H ;
Taubenfeld, G .
SIAM JOURNAL ON COMPUTING, 1997, 26 (02) :539-556
[8]  
Anderson J. H., 1999, Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, P123, DOI 10.1145/301308.301341
[9]   TIME-EFFICIENT AND SPACE-EFFICIENT RANDOMIZED CONSENSUS [J].
ASPNES, J .
JOURNAL OF ALGORITHMS, 1993, 14 (03) :414-431
[10]   Randomized consensus in expected O(Nlog(2)N) operations per processor [J].
Aspnes, J ;
Waarts, O .
SIAM JOURNAL ON COMPUTING, 1996, 25 (05) :1024-1044
123456