Failure detector

In a distributed computing system, a failure detector is a computer application or a subsystem that is responsible for the detection of node failures or crashes.[1] Failure detectors were first introduced in 1996 by Chandra and Toueg in their book Unreliable Failure Detectors for Reliable Distributed Systems. The book depicts the failure detector as a tool to improve consensus (the achievement of reliability) and atomic broadcast (the same sequence of messages) in the distributed system. In other words, failure detectors seek errors in the process, and the system will maintain a level of reliability. In practice, after failure detectors spot crashes, the system will ban the processes that are making mistakes to prevent any further serious crashes or errors.[2][3] In the 21st century, failure detectors are widely used in distributed computing systems to detect application errors, such as a software application stops functioning properly. As the distributed computing projects (see List of distributed computing projects) become more and more popular, the usage of the failure detects also becomes important and critical.[4][5]

## Contents

* 1 Origin
* 1.1 Unreliable failure detector
* 1.2 Failure detector
* 2 Properties
* 2.1 Degrees of completeness
* 2.2 Degrees of accuracy
* 3 Classification
* 4 Applications
* 4.1 Boosting completeness
* 4.2 Reducing a failure detector W to a failure detector S
* 5 See also
* 6 References
* 7 External links

## Origin

### Unreliable failure detector

Chandra and Toueg, the co-authors of the book Unreliable Failure Detectors for Reliable Distributed Systems (1996), approached the concept of detecting failure nodes by introducing the unreliable failure detector.[6] They describe the behavior of a unreliable failure detector in a distributed computing system as: after each process in the system entered a local failure detector component, each local component will examine a portion of all processes within the system.[5] In addition, each process must also contain programs that are currently suspected by failure detectors.[5]

### Failure detector

This picture describes the behavior of a typical failure detector (FD).

Chandra and Toueg claimed that an unreliable failure detector can still be reliable in detecting the errors made by the system.[6] They generalize unreliable failure detectors to all forms of failure detectors because unreliable failure detectors and failure detectors share the same properties. Furthermore, Chandra and Toueg point out an important fact that the failure detector does not prevent any crashes in the system, even if the crashed program has been suspected previously. The construction of a failure detector is an essential, but a very difficult problem that occurred in the development of the fault-tolerant component in a distributed computer system. As a result, the failure detector was invented because of the need for detecting errors in the massive information transaction in distributed computing systems.[1][3][5]

## Properties

The classes of failure detectors are distinguished by two important properties: completeness and accuracy. Completeness means that the failure detectors would find the programs that finally crashed in a process, whereas accuracy means that correct decisions that the failure detectors made in a process.[5]

### Degrees of completeness

The degrees of completeness depend on the number of crashed process is suspected by a failure detector in a certain period.[5]

* Strong completeness: "every faulty process is eventually permanently suspected by every non-faulty process."[6]
* Weak completeness: "every faulty process is eventually permanently suspected by some non-faulty process."[6]

### Degrees of accuracy

The degrees of accuracy depend on the number of mistakes that a failure detector made in a certain period.[5]

* Strong accuracy: "no process is suspected (by anybody) before it crashes."[6]
* Weak accuracy: "some non-faulty process is never suspected."[6]
* Eventual strong accuracy: "no non-faulty process is suspected after some time since the end of the initial period of chaos as the time at which the last crash occurs."[6]
* Eventual weak accuracy: "after some initial period of confusion, some non-faulty process is never suspected."[6]

## Classification

Failure detectors can be categorized in the following eight types:[1][7]

1. Perfect failure detector (P)
2. Eventually perfect failure detectors (♦P)
3. Strong failure detectors (S)
4. Eventually strong failure detectors (♦S)
5. Weak failure detectors (W)
6. Eventually weak failure detectors (♦W)
7. Quasi-perfect failure detectors (Q)
8. Eventually quasi-perfect failure detectors (♦Q)

The properties of these failure detectors are described below:[1]

Accuracy

Complete-
ness

| Strong
Perpetual
Accuracy  | Weak
Perpetual
Accuracy  | Strong
Eventual
Accuracy  | Weak
Eventual
Accuracy

|
|
|
|

Strong Completeness  | P | S | ♦P | ♦S
Weak Completeness  | Q | W | ♦Q | ♦W

In a nutshell, the properties of failure detectors depend on how fast the failure detector detects actual failures and how well it avoids false detection. A perfect failure detector will find all errors without any mistakes, whereas a weak failure detector will not find any errors and make numerous mistakes.[3][8]

## Applications

Different types of failure detectors can be obtained by changing the properties of failure detectors.[3][6] The first examples show that how to increase completeness of a failure detector, and the second example shows that how to change one type of the failure detector to another.

### Boosting completeness

The following is an example abstracted from the Department of Computer Science at Yale University. It functions by boosting the completeness of a failure detector.[6]

initially suspects = ∅

do forever:
for each process p:
if my weak-detector suspects p, then send p to all processes

upon receiving p from some process q:
suspects := suspects + p - q

From the example above, if p crashes, then the weak-detector will eventually suspect it. All failure detectors in the system will eventually suspect the p because of the infinite loop created by failure detectors. This example also shows that a weak completeness failure detector can also suspect all crashes eventually.[6] The inspection of crashed programs does not depend on completeness.[5]

### Reducing a failure detector W to a failure detector S

The following are correctness arguments to satisfy the algorithm of changing a failure detector W to a failure detector S.[1] The failure detector W is weak in completeness, and the failure detector S is strong in completeness. They are both weak in accuracy.[6]

1. It transforms weak completeness into strong completeness.[1]
2. It preserves the perpetual accuracy.[1]
3. It preserves the eventual accuracy.[1]

If all arguments above are satisfied, the reduction of a weak failure detector W to a strong failure detector S will agree with the algorithm within the distributed computing system.[1]

## See also

* Distributed computing
* List of distributed computing projects
* SWIM Protocol
* Crash (computing)
* Fault tolerance
* Consensus
* Atomic broadcast

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 D., Kshemkalyani, Ajay (2008). Distributed computing : principles, algorithms, and systems. Singhal, Mukesh.. Cambridge: Cambridge University Press. ISBN 9780521189842. OCLC 175284075.
2. ↑ Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (2000-04-01). "Failure detection and consensus in the crash-recovery model" (in en). Distributed Computing 13 (2): 99–125. doi:10.1007/s004460050070. ISSN 0178-2770.
3. ↑ 3.0 3.1 3.2 3.3 Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. (April 1985). "Impossibility of Distributed Consensus with One Faulty Process". J. ACM 32 (2): 374–382. doi:10.1145/3149.214121. ISSN 0004-5411.
4. ↑ Holohan, Anne; Garg, Anurag (2005-07-01). "Collaboration Online: The Example of Distributed Computing" (in en). Journal of Computer-Mediated Communication 10 (4): 00. doi:10.1111/j.1083-6101.2005.tb00279.x. ISSN 1083-6101.
5. ↑ 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 Chandra, Tushar Deepak; Toueg, Sam (1996). Unreliable failure detectors for reliable distributed systems. Volume 43 Issue 2. 43. New York, NY, USA: ACM. 225–267. doi:10.1145/226643.226647. ISBN 978-0897914390.
6. ↑ 6.00 6.01 6.02 6.03 6.04 6.05 6.06 6.07 6.08 6.09 6.10 6.11 "FailureDetectors". http://www.cs.yale.edu/homes/aspnes/pinewiki/FailureDetectors.html.
7. ↑ Aguilera, Marcos Kawazoe; Toueg, Sam (1996-10-09). "Randomization and failure detection: A hybrid approach to solve Consensus" (in en). Distributed Algorithms. Lecture Notes in Computer Science. 1151. Springer, Berlin, Heidelberg. pp. 29–39. doi:10.1007/3-540-61769-8_3. ISBN 978-3540617693.
8. ↑ Chen, Wei; Toueg, S.; Aguilera, M. K. (January 2002). "On the quality of service of failure detectors". IEEE Transactions on Computers 51 (1): 13–32. doi:10.1109/12.980014. ISSN 0018-9340.

## External links

* http://www.cs.yale.edu/homes/aspnes/pinewiki/FailureDetectors.html
* http://www.cs.cornell.edu/home/sam/FDpapers.html

* v
* t
* e

Computer science

Note: This template roughly follows the 2012 ACM Computing Classification System.

Hardware|

* Printed circuit board
* Peripheral
* Integrated circuit
* Very Large Scale Integration
* Systems on Chip (SoCs)
* Energy consumption (Green computing)
* Electronic design automation
* Hardware acceleration

Computer systems
organization|

* Computer architecture
* Embedded system
* Real-time computing
* Dependability

Networks|

* Network architecture
* Network protocol
* Network components
* Network scheduler
* Network performance evaluation
* Network service

Software organization|

* Interpreter
* Middleware
* Virtual machine
* Operating system
* Software quality

Software notations
and tools|

* Programming paradigm
* Programming language
* Compiler
* Domain-specific language
* Modeling language
* Software framework
* Integrated development environment
* Software configuration management
* Software library
* Software repository

Software development|

* Software development process
* Requirements analysis
* Software design
* Software construction
* Software deployment
* Software maintenance
* Programming team
* Open-source model

Theory of computation|

* Model of computation
* Formal language
* Automata theory
* Computational complexity theory
* Logic
* Semantics

Algorithms|

* Algorithm design
* Analysis of algorithms
* Algorithmic efficiency
* Randomized algorithm
* Computational geometry

Mathematics
of computing|

* Discrete mathematics
* Probability
* Statistics
* Mathematical software
* Information theory
* Mathematical analysis
* Numerical analysis

Information
systems|

* Database management system
* Information storage systems
* Enterprise information system
* Social information systems
* Geographic information system
* Decision support system
* Process control system
* Multimedia information system
* Data mining
* Digital library
* Computing platform
* Digital marketing
* World Wide Web
* Information retrieval

Security|

* Cryptography
* Formal methods
* Security services
* Intrusion detection system
* Hardware security
* Network security
* Information security
* Application security

Human–computer
interaction|

* Interaction design
* Social computing
* Ubiquitous computing
* Visualization
* Accessibility

Concurrency|

* Concurrent computing
* Parallel computing
* Distributed computing
* Multithreading
* Multiprocessing

Artificial
intelligence|

* Natural language processing
* Knowledge representation and reasoning
* Computer vision
* Automated planning and scheduling
* Search methodology
* Control method
* Philosophy of artificial intelligence
* Distributed artificial intelligence

Machine learning|

* Supervised learning
* Unsupervised learning
* Reinforcement learning
* Multi-task learning
* Cross-validation

Graphics|

* Animation
* Rendering
* Image manipulation
* Graphics processing unit
* Mixed reality
* Virtual reality
* Image compression
* Solid modeling

Applied
computing|

* E-commerce
* Enterprise software
* Computational mathematics
* Computational physics
* Computational chemistry
* Computational biology
* Computational social science
* Computational engineering
* Computational healthcare
* Digital art
* Electronic publishing
* Cyberwarfare
* Electronic voting
* Video games
* Word processing
* Operations research
* Educational technology
* Document management

* Book
* Category
* Outline
* WikiProject
* Commons

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Failure detector. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Failure_detector&oldid=201434"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template