Synchronous system and perfect failure detector: Solvability and efficiency issues
Bernadette Charron-Bost, Rachid Guerraoui, A. Schiper · 2002
We compare, in terms of solvability and efficiency, the synchronous model, noted Ss, with the asynchronous model augmented with a perfect failure detector, noted S/sub P/. We first exhibit a problem that, although time-free, is solvable in S/sub S/ but not in S/sub P/. We then examine whether one of these two models allows more efficient solutions for designing fault-tolerant applications. In particular, we concentrate on the uniform consensus problem which is solvable in both models, and we design a uniform consensus algorithm for the S/sub S/ model that is more efficient than any algorithm solving uniform consensus in S/sub P/ with respect to some significant time complexity measure. From a practical viewpoint, the synchronous model thus seems better than the asynchronous model augmented with a perfect failure detector.