TY - JOUR
T1 - Certifying algorithms
AU - McConnell, R. M.
AU - Mehlhorn, K.
AU - Näher, S.
AU - Schweitzer, P.
PY - 2011/5
Y1 - 2011/5
N2 - A certifying algorithm is an algorithm that produces, with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying algorithm inputs x, receives the output y and the certificate w, and then checks, either manually or by use of a program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust the algorithm.We put forward the thesis that certifying algorithms are much superior to non-certifying algorithms, and that for complex algorithmic tasks, only certifying algorithms are satisfactory. Acceptance of this thesis would lead to a change of how algorithms are taught and how algorithms are researched. The widespread use of certifying algorithms would greatly enhance the reliability of algorithmic software.We survey the state of the art in certifying algorithms and add to it. In particular, we start a theory of certifying algorithms and prove that the concept is universal.
AB - A certifying algorithm is an algorithm that produces, with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying algorithm inputs x, receives the output y and the certificate w, and then checks, either manually or by use of a program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust the algorithm.We put forward the thesis that certifying algorithms are much superior to non-certifying algorithms, and that for complex algorithmic tasks, only certifying algorithms are satisfactory. Acceptance of this thesis would lead to a change of how algorithms are taught and how algorithms are researched. The widespread use of certifying algorithms would greatly enhance the reliability of algorithmic software.We survey the state of the art in certifying algorithms and add to it. In particular, we start a theory of certifying algorithms and prove that the concept is universal.
KW - Algorithms
KW - Certification
KW - Software reliability
UR - http://www.scopus.com/inward/record.url?scp=79955010067&partnerID=8YFLogxK
U2 - 10.1016/j.cosrev.2010.09.009
DO - 10.1016/j.cosrev.2010.09.009
M3 - Article
SN - 1574-0137
VL - 5
SP - 119
EP - 161
JO - Computer Science Review
JF - Computer Science Review
IS - 2
ER -