Revisiting the relationship between election and consensus in asynchronous distributed systems

被引：0

作者：

Park, SH ^{[1
]}

Cho, MH ^{[1
]}

机构：

[1] Namseoul Univ, Sungwhan Up, Chung Nam, South Korea

来源：

PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS | 2001年

关键词：

election; consensus; failure detectors; asynchronous distributed systems;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper discusses the relationship between the Election problem and the Consensus problem in asynchronous systems with unreliable failure detectors. Me first confirm that Leader Election is harder than Consensus, In Contrast 10 Consensus, Election is impossible to solve with unreliable failure detectors even with a single crash failure, More precisely, the weakest failure detector that is needed to solve this problem is a Perfect Failure Detector, which is strictly stronger than the weakest failure detector that is needed to solve Consensus, H use a reduction protocol to show that Election is harder than Consensus.

引用

页码：913 / 918

页数：4

共 19 条

[1] ELECTION IN ASYNCHRONOUS COMPLETE NETWORKS WITH INTERMITTENT LINK FAILURES
ABUAMARA, H
LOKRE, J
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (07) : 778 - 788
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3] Bernstein P.A., 1987, Concurrency Control and Recovery in Database Systems
[4] Design and analysis of dynamic leader election protocols in broadcast networks
Brunekreef, J
Katoen, JP
Koymans, R
Mauw, S
[J]. DISTRIBUTED COMPUTING, 1996, 9 (04) : 157 - 171
[5] Unreliable failure detectors for reliable distributed systems
Chandra, TD
Toueg, S
[J]. JOURNAL OF THE ACM, 1996, 43 (02) : 225 - 267
[6] The weakest failure detector for solving Consensus
Chandra, TD
Hadzilacos, V
Toueg, S
[J]. JOURNAL OF THE ACM, 1996, 43 (04) : 685 - 722
[7] DOLEV D, 1987, LECT NOTES COMPUTER, V448, P42
[8] FISCHER M, 1985, J ACM, P374
[9] FROMENTIN E, 1999, P DISTR COMP C IEEE
[10] GARCIAMOLINA H, 1982, IEEE T COMPUT, V31, P49

← 1 2 →