On the weakest failure detector for hard agreement problems

作     者：Larrea, M 

作者机构：Univ Basque Country Dept Comp Architecture & Technol San Sebastian Spain 

出 版 物：《JOURNAL OF SYSTEMS ARCHITECTURE》 (系统结构杂志)

年 卷 期：2003年第49卷第7-9期

页      面：345-353页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：MCYT, (TIC2001-1586-C03-01) Consejo Superior de Investigaciones Científicas, CSIC 

主　　题：distributed computing fault-tolerance failure detector consensus atomic commit terminating reliable broadcast 

摘      要：Chandra and Toueg [J. ACM 43 (1996) 225] and Fromentin et al. [Proc. IEEE Internal. Conf. on Distrib. Comput., 1999, p. 470], respectively, stated that the weakest failure detector for any of non-blocking atomic commitment and terminating reliable broadcast is the perfect failure detector P. Recently, Guerraoui [IPL 79 (2001) 99] presented a counterexample of those results, exhibiting a failure detector called Marabout (M) that is incomparable to P and yet solves those problems. In this paper we present three new perfect failure detector classes as alternatives to P and M. All our classes are weaker than P. Furthermore, two of them are also weaker than M, and yet solve non-blocking atomic commitment and terminating reliable broadcast. Interestingly, our failure detector classes are implementable whenever P is implementable (e.g., in a synchronous system), which is not the case with M. (C) 2003 Elsevier B.V. All rights reserved.