TY - GEN
T1 - Synchronous system and perfect failure detector
T2 - 2000 International Conference on Dependable Systems and Networks, DSN 2000
AU - Charron-Bost, Bernadette
AU - Guerraoui, Rachid
AU - Schiper, André
PY - 2000/1/1
Y1 - 2000/1/1
N2 - We compare, in terms of solvability and efficiency, the synchronous model, noted SS, with the asynchronous model augmented with a perfect failure detector, noted SP. We first exhibit a problem that, although time-free, is solvable in SS but not in SP. 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 SS model that is more efficient than any algorithm solving uniform consensus in SP 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.
AB - We compare, in terms of solvability and efficiency, the synchronous model, noted SS, with the asynchronous model augmented with a perfect failure detector, noted SP. We first exhibit a problem that, although time-free, is solvable in SS but not in SP. 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 SS model that is more efficient than any algorithm solving uniform consensus in SP 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.
U2 - 10.1109/ICDSN.2000.857585
DO - 10.1109/ICDSN.2000.857585
M3 - Conference contribution
AN - SCOPUS:0034590391
SN - 0769507085
SN - 9780769507088
T3 - Proceedings of the 2002 International Conference on Dependable Systems and Networks
SP - 523
EP - 532
BT - Proceedings - International Conference on Dependable Systems and Networks, DSN 2000
PB - IEEE Computer Society
Y2 - 25 June 2000 through 28 June 2000
ER -