IEEE Transactions on Reliability · 2004 · 138 citations · 64 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsFault-tolerant ComputingFault-tolerant SystemsDependability AnalysisError DetectionReliable System DesignSafety-critical Embedded SystemsSafety-critical SystemsSoftware Fault ToleranceFunctional Group ClassificationFunctional Level ClassificationN-version ProgrammingRedundant Systems DesignSafety-critical ArchitectureSafety-critical SoftwareSafety-critical Software Engineering
Voting algorithms are used to provide an error masking capability in a wide range of highly dependable commercial & research applications. These applications include N-Modular Redundant hardware systems and diversely designed software systems based on N-Version Programming. The most sophisticated & complex algorithms can even tolerate malicious (or Byzantine) subsystem errors. The algorithms can be implemented in hardware or software depending on the characteristics of the application, and the type of voter selected. Many voting algorithms have been defined in the literature, each with particular strengths and weaknesses. Having surveyed more than 70 references from the literature, a functional classification is used in this paper to provide taxonomy of those voting algorithms used in safety-critical applications. We classify voters into three categories: generic, hybrid, and purpose-built voters. Selected algorithms of each category are described, for illustrative purposes, and application areas proposed. Approaches to the comparison of algorithm behavior are also surveyed. These approaches compare the acceptability of voter behavior based on either statistical considerations (e.g., number of successes, number of benign or catastrophic results), or probabilistic computations (e.g., probability of choosing correct value in each voting cycle or average mean square error) during q voting cycles.
64
Weighted voting for replicated data
David K. Gifford · 1979 · 1.3K citations · Full text
D. R. K. Brownrigg · Communications of the ACM · 1984 · 799 citations · Full text
The Byzantine generals strike again
Danny Dolev · Journal of Algorithms · 1982 · 573 citations