Fast Asynchronous Uniform Consensus in Real-Time Distributed Systems

Abstract—We investigate whether asynchronous computational models and asynchronous algorithms can be considered for designing real-time distributed fault-tolerant systems. A priori, the lack of bounded finite delays is antagonistic with timeliness requirements. We show how to circumvent this apparent contradiction, via the principle of “late binding ” of a solution to some (partially) synchronous model. This principle is shown to maximize the coverage of demonstrated safety, liveness, and timeliness properties. These general results are illustrated with the Uniform Consensus (UC) and the Real-Time UC problems, assuming processor crashes and reliable communications, considering asynchronous solutions based upon Unreliable Failure Detectors. We introduce the concept of Fast Failure Detectors and we show that the problem of building Strong or Perfect Fast Failure Detectors in real systems can be stated as a distributed message scheduling problem. A generic solution to this problem is given, illustrated considering deterministic Ethernets. In passing, it is shown that, with our construction of Unreliable Failure Detectors, asynchronous algorithms that solve UC have a worst-case termination lower bound that matches the optimal synchronous lower bound, that is, \u85 t 1D, where t is the maximum number of processors that may crash and D is the maximum interprocess message delay. Finally, we introduce FastUC, a novel solution to UC, that is based upon Fast Failure Detectors. FastUC has a worst-case termination time that is sublinear in tD. For most practical cases and common values of t, FastUC terminates in D, making it a worst-case time optimal solution to Real-Time UC. Index Terms—Asynchronous computational models, partially synchronous computational models, coverage, uniform consensus, real-time distributed fault-tolerant computing, safety, liveness, timeliness, unreliable failure detectors, schedulability analysis. æ