@inproceedings{chen2007failure,
author = {Chen, Wei and Zhang, Jialin and Chen, Yu and Liu, Xuezheng},
title = {Failure Detectors and Extended Paxos for k-Set Agreement},
booktitle = {Proceedings of the 13th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'2007), Melbourne, Australia, Dec. 2007.},
year = {2007},
month = {December},
abstract = {Failure detector class Ω k has been defined in [17] as an extension to failure detector ­Ω, and an algorithm has been given in [15] to solve k-set agreement using Ω ­k in asynchronous message-passing systems. In this paper, we extend these previous works 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 and thus serves as a good basis for the partitioned failure detectors we introduce in [6]. 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 [11], and thus it inherits the efficiency, flexibility, and robustness of the Paxos algorithm. In particular, it has better message complexity than the algorithm in [15]. Both the new failure detectors and the new algorithm enrich our understanding of the k-set agreement problem. In particular, they serve as the basis of our study on partitioned failure detectors for k-set agreement [6].},
url = {http://approjects.co.za/?big=en-us/research/publication/failure-detectors-and-extended-paxos-for-k-set-agreement/},
pages = {19},
edition = {Proceedings of the 13th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'2007), Melbourne, Australia, Dec. 2007.},
}