Warns, Timo, Freiling, Felix C. and Hasselbring, Wilhelm (2006) Solving Consensus Using Structural Failure Models. [Paper] In: 25th IEEE Symposium on Reliable Distributed Systems (SRDS 2006). , 2-4 October 2006 , Leeds, UK . Proceedings of the 25th IEEE Symposium on Reliable Distributed Systems (SRDS 2006). ; 212 -224 . DOI 10.1109/SRDS.2006.44.

Preview

Text SRDS2006.pdf Download (171kB) | Preview

Abstract

Failure models characterise the expected failures in fault-tolerant computing. Such models must be expressive enough to cover all relevant practical situations, but they must also be simple enough to allow uncomplicated reasoning about fault-tolerant algorithms. Usually, an increase in expressiveness improves the resilience of solutions, but complicates formal reasoning. In this paper, we introduce the class of structural failure models DiDep that allows to specify directed dependent failures, which, for example, occur in the area of intrusion tolerance and security. DiDep is a generalisation of previous models for undirected dependent failures, namely the general adversary structures, the fail-prone systems, and the core and survivor sets, which we show to be equivalent. We show that the increase in expressiveness of DiDep does not significantly penalise the simplicity of corresponding models by giving an algorithm that transforms any Consensus algorithm for undirected dependent failures into a Consensus algorithm for a DiDep model. Exemplarily, we give a Consensus algorithm using failure detectors for general adversary structures and transform it to be used with a DiDep model. We characterise the improved resilience obtained with DiDep and show that certain models even allow to circumvent the famous FLP impossibility result.

Actions (login required)

View Item