Timed uniform consensus resilient to crash and timing faults
Tomoko Izumi, Akinori Saitoh, Toshimitsu Masuzawa · 2004
/spl Delta/-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 /spl Delta/ (/spl Delta/-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the /spl Delta/-timed uniform consensus problem in presence of f/sub t/ crash processes and f/sub c/ timing-faulty processes. This paper proposes a /spl Delta/-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the /spl Delta/-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 /spl Delta/-timed uniform consensus. However, as long as f/sub 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 /spl Delta/-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 /spl Delta/-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.