6. Designing Algorithms for Dependent Process Failures
Flavio Junqueira7
and Keith Marzullo7 
| (7) |
Department of Computer Science and Engineering, University of California, San Diego |
Abstract
Most fault-tolerant algorithms are designed assuming that out of n components, no more than t can be faulty. For example, solutions to the Consensus problem are usually developed assuming
no more than t of the n processes are faulty, where “being faulty” is specialized by a failure model. We call this the t of n assumption (also known as threshold model). It is a convenient assumption to make. For example, bounds are easily expressed
as a function of t: if processes can fail only by crashing, then the Consensus problem is solvable when t
< n if the system is synchronous and when t < 2n if the system is asynchronous extended with a failure detector of the class ◊W. [5.5], [5.1]
This work was developed in the context of the RAMP project, supported by DARPA as project number N66001-01-1-8933.
The author is partially supported by a scholarship from CAPES.
References secured to subscribers.