Latency Measures and Lower Bounds for Consensus with Failure Detectors

摘要

In this paper we propose complexity measures for fault-tolerant algorithms using failure detectors. These measures are based on the latency (size of the message chain) and depend on the number of effective crashes and the properties of failure detection. We use these measures to give some greatest lower bounds for the Uniform Consensus Problem with various classes of failure detectors. In particular, we show that the classical latency measure is not really appropriate to evaluate the performances of consensus algorithms. We also prove a result showing that for the strong failure detector the greatest lower bound for the Consensus Problem is independent of the number of crashes.