Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: The correct process terminates its execution within a constant time Δ(Δ-timeliness), and no two processes decide differently (Uniformity). In this paper, we consider the A-timed uniform consensus problem in presence of f{sub}t crash processes and f{sub}c timing-faulty processes. This paper proposes a Δ-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the Δ-timed uniform consensus when at least f{sub}t + 1 correct processes exist in the system. If the system has less than f{sub}t + 1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as f{sub}t +1 processes are alive, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to f{sub}t timing-faulty processes requires that the system has at least f{sub}t + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to f{sub}t timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f{sub}t + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.
展开▼
