In a previous post, I discussed the notion of Schrödinger CRCs, first described by Kevin Driscoll et al. in their paper Byzantine Fault Tolerance, from Theory to Reality. The basic idea is that error-detecting codes do not necessarily prevent two receivers from obtaining messages that are semantically different (i.e., different data) but syntactically valid (i.e., the CRC matches the respective data words received). The upshot is that even with CRCs, you can suffer Byzantine faults, with some probability.
… So what is that probability of a Schrödinger’s CRC? That’s the topic of this post—which cleans up a few of the ideas I presented earlier. I published a short paper on the topic, which I presented at Dependable Sensors and Networks, 2010, while Kevin Driscoll was in the audience! If you’d prefer to read the PDF or get the slides, they’re here. The simulation code (Haskell) is here.
Tags: Byzantine fault, CRC, Fault Tolerance, Haskell
February 4, 2010 at 7:49 am |
> In particular, is the Schrödinger Hamming Distance ever strictly greater than the Hamming Distance?
How about the following code: Encode a 0 bit as 01 and a 1 bit as 10. Now all valid codes have the same number of 1s and 0s. Now *all* Schrödinger type errors can be detected, while the Hamming Distance is only 2.
March 14, 2010 at 5:04 pm |
[Sorry the delayed response.]
That’s clever; you’re right. What you propose isn’t technically a CRC, I think, as any bit-stream should be a potentially-valid message, if it is accompanied with the appropriate CRC.