“Schrodinger’s Probability” for Error-Checking Codes

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.

View this document on Scribd
About these ads

Tags: , , ,

2 Responses to ““Schrodinger’s Probability” for Error-Checking Codes”

  1. Twan van Laarhoven Says:

    > 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.

    • Lee Pike Says:

      [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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: