Premium
A framework for the design of dependent‐failure algorithms
Author(s) -
Junqueira Flavio,
Marzullo Keith
Publication year - 2007
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1170
Subject(s) - replication (statistics) , computer science , independent and identically distributed random variables , class (philosophy) , set (abstract data type) , process (computing) , distributed computing , algorithm , distributed algorithm , theoretical computer science , mathematics , random variable , programming language , artificial intelligence , statistics
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 All mathematics should have $n > k\cdot 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 © 2007 John Wiley & Sons, Ltd.