Validation is done after the handling of side effects, and the adjustments of status information. By that time, if a re-execution is repeating its original execution, the set of mutations incurred on the surrogate should be the same as that on the client. Since mutations are captured on CMLs, our file system can validate a re-execution by comparing the relevant portion of the CML of the surrogate to that of the client.
To facilitate the comparison, the client packs every record in the relevant portion of the CML as part of the operation log. However, the container files, which are associated with STORE records, are not packed; otherwise they would incur a heavy network traffic for shipping the operation log, amounting to the traffic needed for value shipping. Instead, the client packs the fingerprint of each container file. When comparing CMLs, the surrogate asserts that two container files are equal if they have the same fingerprint.
A fingerprint function produces a fixed-length fingerprint f(M) for a given arbitrary-length message M. A good fingerprint function should have two properties: (1) computing f(M) from M is easy, and (2) the probability that another message M' gives the same fingerprint is small. For our purpose, the messages for which we find the fingerprints are the contents of the container files.
Our file system employs MD5 (Message Digest 5) fingerprints [17,21]. Each fingerprint has 128 bits, so the overhead is very small. Also, the probability that two different container files give the same fingerprint is very small; it is in the order of 1/264.
The fact that the probability is non-zero, albeit very small, may worry some readers. However, even value shipping is vulnerable to a small but non-zero probability of error. That is, there is a small probability that a communication error has occurred but is not detected by the error-correction subsystem of the communication channel. We believe people can tolerate the small probabilities of errors of both operation shipping and value shipping.