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 条

[11] A SIMPLE AND EFFICIENT RANDOMIZED BYZANTINE AGREEMENT ALGORITHM [J].

CHOR, B ;

COAN, BA .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1985, 11 (06) :531-539

[12]

CHOR B, 1987, RANDOMIZATION BYZANT, V4

[13]

CHOR B, 1985, 4TH P ANN ACM S PRIN, P152

[14]

CHOR B, 1987, ACM PODC, P86

[15]

COAN BA, 1986, 5TH P ACM S PRINC DI, P40

[16] ON THE MINIMAL SYNCHRONISM NEEDED FOR DISTRIBUTED CONSENSUS [J].

DOLEV, D ;

DWORK, C ;

STOCKMEYER, L .

JOURNAL OF THE ACM, 1987, 34 (01) :77-97

[17]

Dwork C., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P222, DOI 10.1109/SFCS.1986.20

[18]

FELDMAN P, 1988, 20TH P S THEOR COMP, P148

[19]

Feller W., 1957, INTRO PROBABILITY TH, V1

[20]

FISCHER M, 1985, J ASS COMPUT MACH, V32

← 1 2 3 4 →