Synchronous System and Perfect Failure Detector: solvability and efficiency issues

Keywords: distributed systems, fault-tolerance, consensus, efficiency, synchronous system, asynchronous system, failure detector. We compare, in terms of solvability and efficiency, the synchronous model, noted S_S, with the asynchronous model augmented with a perfect failure detector, noted S_P. We first exhibit a problem that, although time-free, is solvable in S_S but not in S_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_S model that is more efficient than any algorithm solving uniform consensus in S_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.

Published in:
Proceedings of the IEEE Int. Conf. on Dependable Systems and Networks (DSN), 523-532
IEEE Computer Society

 Record created 2005-05-20, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)