Failure Detectors and Extended Paxos for k-Set Agreement
Wei Chen, Jialin Zhang, Yu Chen, Xuezheng Liu · 2007
Failure detector class Omegakappahas been defined in (G. Neiger, 1995) as an extension to failure detector Omega, and an algorithm has been given in (A. Mostefaoui et al., 2005) to solve k-set agreement using Omegakappain asynchronous message-passing systems. In this paper, we extend these previous work in two directions. First, we define two new classes of failure detectors Omegakappa'and Omegakappa",which are new ways of extending Omega and show that they are equivalent to Omegakappa. Class Omegakappa'is more flexible than Omegakappain that it does not require the outputs to stabilize eventually, while class Omegakappa"does not refer to other processes in its outputs. Second, we present a new algorithm that solves k-set agreement using Omegakappa"when a majority of processes do not crash. The algorithm is a faithful extension of the Paxos algorithm (L. Lamport, 1998), and thus it inherits the efficiency, flexibility, and robustness of the Paxos algorithm. In particular, it has better message complexity than the algorithm in (A. Mostefaoui et al., 2005). Both the new failure detectors and the new algorithm enrich our understanding of the k-set agreement problem.