Freiling, F. C. and Jhumka, Arshad (2007) Global predicate detection in distributed systems with small faults. In: 9th International Symposium on Stabilisation, Safety and Security of Distributed Systems, Paris, France, 14-16 Nov 2007 . Published in: Proceedings of the 9th International Symposium on Stabilisation, Safety and Security of Distributed Systems pp. 296-310.

Abstract

We study the problem of global predicate detection in presence of permanent and transient failures. We term the transient failures as small faults. We show that it is impossible to detect predicates in an asynchronous distributed system prone to small faults even if nodes are equipped with a powerful device known as failure detector sequencer (denoted by Σ). To redress this impossibility, we introduce a theoretical de- vice, known as a small fault sequencer (denoted by ΣSF ), and show that ΣSF is necessary and sufficient for predicate detection. Unfortunately,we also show that ΣSF cannot be implemented even in a synchronous dis- tributed system. Fortunately, however, we show that predicate detection can be achieved with high probability in synchronous systems.

Request changes to a record

Actions (login required)

View Item