Failure Detectors and Extended Paxos for k-Set Agreement

Wei Chen, Jialin Zhang, Yu Chen, and Xuezheng Liu

May 2007

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].

Publication type | TechReport |

Number | MSR-TR-2007-48 |

Pages | 19 |

Institution | Microsoft Research |

- Decentralized, Connectivity-Preserving, and Cost-Efffective Structured Overlay Maintenance
- Note on the Hardness of Bounded Budget Betweenness Centrality Game with Path Length Constraints
- Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks

> Publications > Failure Detectors and Extended Paxos for k-Set Agreement