Abstract | ||
---|---|---|
Failure detector class k has been defined in [18] as an extension to failure detector , and an algorithm has been given in [16] to solve k-set agreement using k in asynchronous message-passing systems. In this paper, we extend these previous work in two directions. First, we define two new classes of failure detectors k and k, which are new ways of extending , and show that they are equivalent to k. Class k is more flexible than k in that it does not require the outputs to stabilize eventually, while class k does not refer to other processes in its outputs. Second, we present a new algorithm that solves k-set agreement using k when a majority of processes do not crash. The algorithm is a faithful extension of the Paxos algorithm [12], and thus it inherits the efficiency, flexibility, and robustness of the Paxos algorithm. In particular, it has better message complexity than the algorithm in [16]. Both the new failure detectors and the new algorithm enrich our understanding of the k-set agreement problem. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1109/PRDC.2007.34 | PRDC |
Keywords | Field | DocType |
message passing,communication complexity,failure detector,set theory | Asynchronous communication,Set theory,Computer science,Real-time computing,Theoretical computer science,Communication complexity,Robustness (computer science),Detector,Message passing,Paxos,Distributed computing,Chandra–Toueg consensus algorithm | Conference |
ISBN | Citations | PageRank |
0-7695-3054-0 | 6 | 0.46 |
References | Authors | |
29 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wei Chen | 1 | 3416 | 170.71 |
Jialin Zhang | 2 | 39 | 3.51 |
Yu Chen | 3 | 128 | 28.58 |
Xuezheng Liu | 4 | 352 | 22.72 |