FAST RANDOMIZED CONSENSUS USING SHARED MEMORY

被引：138

作者：

ASPNES, J

HERLIHY, M

机构：

[1] CARNEGIE MELLON UNIV,SCH COMP SCI,PITTSBURGH,PA 15213

[2] DIGITAL EQUIPMENT CORP,CAMBRIDGE RES LAB,CAMBRIDGE,MA 02139

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0196-6774(90)90021-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers. The fastest previously known algorithm has exponential expected running time. Our algorithm is polynomial, requiring an expected O(n4) operations. Applications of this algorithm include the elimination of critical sections from concurrent data structures and the construction of asymptotically unbiased shared coins. © 1990.

引用

页码：441 / 461

页数：21

共 35 条

[1]

ABRAHAMSON K, 1988, 7TH ACM SIGACT SIGOP

[2]

[Anonymous], COMMUNICATION

[3]

ATTIYA H, 1989, 8TH P ACM S PRINC DI, P281

[4]

BARNOY A, 1989, 8TH P ANN ACM S PRIN, P307

[5]

Ben-Or M., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P408, DOI 10.1109/SFCS.1985.15

[6]

BENOR M, 1983, 2ND P ANN ACM S PRIN, P27

[7]

BLOOM B, 1987, 6TH ACM SIGACT SIGOP, P249

[8]

BRACHA G, 1983, 2ND P ANN ACM S PRIN, P12

[9]

BRACHA G, 1985, 17TH ANN S THEOR COM

[10]

Broder A. Z., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P157, DOI 10.1109/SFCS.1984.715912

← 1 2 3 4 →