A comparison of voting algorithms for n-version programming

Abstract

One approach to software fault-tolerance is to develop three versions of a program from a common specification, execute these versions in parallel, and vote on the output. If two versions agree, this majority vote is taken as the correct result. Errors in a single version are thus masked out. If there is no majority, a 3-version failure occurs. In earlier experimental work, groups of versions were tested in 3- version programming mode and the resulting average failure probability compared with the average failure probability of the individual versions. This paper describes the use of 5 alternative voting algorithms and compares the resulting failure probabilities against the failure probability for standard 3-version programming. All algorithms produced an improvement over standard 3-version programming, and one algorithm was sometimes able to produce entirely correct values even when none of the three versions has done so.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>