Three-processor tasks are undecidable

被引：40

作者：

Gafni, E ^{[1
]}

Koutsoupias, E ^{[1
]}

机构：

[1] Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90095 USA

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 03期

关键词：

asynchronous distributed computation; task-solvability; wait-free computation; contractibility problem;

D O I：

10.1137/S0097539796305766

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that no algorithm exists for deciding whether a finite task for three or more processors is wait-free solvable in the asynchronous read-write shared-memory model. This impossibility result implies that there is no constructive (recursive) characterization of wait-free solvable tasks. It also applies to other shared-memory models of distributed computing, such as the comparison-based model.

引用

页码：970 / 983

页数：14

共 19 条

[1]

Biran O., 1988, Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, P263, DOI 10.1145/62546.62590

[2]

Borowsky E., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P91, DOI 10.1145/167088.167119

[3]

BOROWSKY E, 1995, THESIS U CALIFORNIA

[4] Concerning the topology of three dimensional space [J].

Dehn, M .

MATHEMATISCHE ANNALEN, 1910, 69 :137-168

[5]

Dey TK, 1995, AN S FDN CO, P266, DOI 10.1109/SFCS.1995.492482

[6] IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS [J].

FISCHER, MJ ;

LYNCH, NA ;

PATERSON, MS .

JOURNAL OF THE ACM, 1985, 32 (02) :374-382

[7]

Gafni E., 1995, Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, DOI 10.1145/224964.225009

[8]

Herlihy M., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P111, DOI 10.1145/167088.167125

[9]

HERLIHY M, 1994, P 26 ACM S THEOR COM, P101

[10]

HERLIHY M, 1996, CS9603 BROWN U DEP C

← 1 2 →