An introduction to oracles for asynchronous distributed systems

被引：13

作者：

Mostefaoui, A ^{[1
]}

Mourgaya, E ^{[1
]}

Raynal, M ^{[1
]}

机构：

[1] IRISA, F-35042 Rennes, France

来源：

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2002年 / 18卷 / 06期

关键词：

asynchronous distributed system; consensus; distributed oracle; fair lossy channel; fault-tolerance; process crash; quiescent protocol; random number; uniform reliable broadcast; unreliable failure detector;

D O I：

10.1016/S0167-739X(02)00048-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper is an introduction to oracles the aim of which is to help solving distributed computing problems in asynchronous distributed systems prone to process crash failures and fair lossy channels. Actually, the combination of asynchrony and failures makes a lot of problems impossible to solve in unreliable asynchronous distributed systems. Hence, those systems have to be extended with appropriate oracles in order these problems become solvable. Using two such problems (namely, the design of a quiescent uniform reliable broadcast facility, and the consensus problem), this paper presents appropriate oracles allowing to solve these problems. In that sense, the paper is a guided tour to the definition of oracles suited to unreliable asynchronous distributed systems. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：757 / 767

页数：11

共 25 条

[1] Aguilera MK, 1999, LECT NOTES COMPUT SC, V1693, P19
[2] Aguilera MK, 1999, SIAM J COMPUT, V28, P890, DOI 10.1137/S0097539796312915
[3] On quiescent reliable communication
Aguilera, MK
Chen, W
Toueg, S
[J]. SIAM JOURNAL ON COMPUTING, 2000, 29 (06) : 2040 - 2073
[4] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[5] ATTIYA H, 1998, DISTRIBUTED COMPUTIN
[6] Ben-Or Michael, 1983, Proceedings of the second ACM Symposium on Principles of Distributed Computing (PODC), P27
[7] ASYNCHRONOUS CONSENSUS AND BROADCAST PROTOCOLS
BRACHA, G
TOUEG, S
[J]. JOURNAL OF THE ACM, 1985, 32 (04) : 824 - 840
[8] Unreliable failure detectors for reliable distributed systems
Chandra, TD
Toueg, S
[J]. JOURNAL OF THE ACM, 1996, 43 (02) : 225 - 267
[9] The weakest failure detector for solving Consensus
Chandra, TD
Hadzilacos, V
Toueg, S
[J]. JOURNAL OF THE ACM, 1996, 43 (04) : 685 - 722
[10] MORE CHOICES ALLOW MORE FAULTS - SET CONSENSUS PROBLEMS IN TOTALLY ASYNCHRONOUS SYSTEMS
CHAUDHURI, S
[J]. INFORMATION AND COMPUTATION, 1993, 105 (01) : 132 - 158

← 1 2 3 →