Adaptive timeliness of consensus in presence of crash and timing faults

作     者：Izumi, Taisuke Saitoh, Akinori Masuzawa, Toshimitsu 

作者机构：Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan Tottori Univ Environm Studies Fac Environm & Informat Studies Tottori 6891111 Japan 

出 版 物：《JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING》 (并行与分布式计算杂志)

年 卷 期：2007年第67卷第6期

页      面：648-658页

核心收录：

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

基　　金：Japan Society for the Promotion of Science, KAKEN, (15300017) Ministry of Education, Culture, Sports, Science and Technology, MEXT 

主　　题：distributed algorithm timeliness property consensus problem crash fault timing fault 

摘      要：The Delta-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Delta (Delta-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Delta-timed uniform consensus problem in presence of f(c) crash processes and f(t) timing-faulty processes, and propose a Delta-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Delta-timed uniform consensus when at least f(t) + 1 correct processes exist in the system. If the system has less than f(t) + 1 correct processes, the algorithm cannot solve the Delta-timed uniform consensus. However, as long as f(t) + 1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Delta-timed uniform consensus algorithm tolerating up to f(t) timing-faulty processes requires that the system has at least f(t) + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any A-timed uniform consensus algorithm tolerating up to f(t) timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f(t) + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. (c) 2007 Elsevier Inc. All rights reserved.