This research investigates a technique which allows computer programs to be constructed which are more easily and efficiently tested and which can be incorporated into a design methodology for producing efficiently testable and fault tolerant software systems. The technique is to modify a primary applications program so that, with essentially negligible overhead, the primary program not only produces its required output but also generates additional data, referred to as a ``certification trail.'' The certification trail allows the correctness of the primary program's output to be completely and efficiently certified by means of a second, simpler and more efficiently executed program, referred to as a ``certifier'' which uses the certification trail to also produce the output so that a subsequent comparison operation can take place. The relative simplicity of the certifier has significant advantages beyond that of speed of execution. For example, the certifier program can be formally verified for correctness in cases where doing so for the primary program is much more complicated --- perhaps prohibitively so. In general, this project develops a formal, theoritical framework for the certification trail technique, as well as for building upon proof-of-concept performance experimentation by means of implementing the technique and generating performance data for primary programs implementing a variety of well-known algorithms.
