A framework for the design of dependent-failure algorithms
Dependent failures constitute a real problem in distributed systems. In this paper, we present a framework for the design of distributed algorithms for systems in which failures of processes are not necessarily independent or identically distributed. To derive this framework, we revisit the traditional way of designing distributed algorithms: assuming a threshold t on the number of process failures and determining constraints on process replication of the form n > k center dot t. Under this model, there are several important results in the literature, and we use observations from these results to derive a framework that enables more expressive characterizations of failures, but still captures the essence of previous results. Our framework then has two parts: a characterization of the subsets of processes that can fail in an execution and properties that express constraints on process replication, called replication predicates. After presenting our model to characterize failures, we first consider a class of replication predicates that represent most well-known problems in distributed computing. Second, we extend this set to also include some predicates for problems that have unusual bounds. We argue that, although being unusual, they have important practical implications, such as using fewer replicas. Copyright (c) 2007 John Wiley & Sons, Ltd.
dependent failures distributed algorithms replication fault tolerance