Welcome to MathOverflow

Question

2

Suppose you have some storage medium of a given size M, and can make some kind of backup on another medium of size B with M > B. You can choose the scheme to determine the contents of the backup.

After you made that partial backup, an adversary (or a random process) will make a number of changes to your original medium. Given the changed medium and your partial backup, your task is to restore the original state of your medium. How many changes could you undo? What is the theoretical maximum? And how successful are the schemes you can come up with?

I have toyed with this question for a while. Obviously, in general you can not hope to undo more than B changes. Viewed more mathematical, I am looking for a systematic code that works with huge block sizes.

flag	asked May 24 2012 at 18:11 Matthias Goergens 53●4

1

This question differs from the ones I've seen discussed in coding theory, because you're given that errors can be introduced only into the original medium, not into the backup. (Note that I wrote "I've seen" --- there's plenty of coding theory that I haven't seen, and questions like this may well have been treated there.) – Andreas Blass May 24 2012 at 18:31

1

I would start calculations based on Reed-Solomon code, but it has the following obvious drawbacks: 1) it will correct data only in chunks that are multiples of the size of the field element (=symbol), 2) the larger the total package M+B, the larger will the symbols have to be: with $r$ bit symbols the maximum size of M+B is $r\cdot 2^r$ bits, 3) the amount of corrupted data is counted in terms of the affected symbols, so if the adversary changes a single bit of a symbol, the entire symbol is corrupted, 4) it won't take advantage of the fact that the errors are all in the original. – Jyrki Lahtonen May 24 2012 at 19:25

1

...(continue, sorry). So I would like to know a little bit more about what kind of errors the adversary will be able to induce. Do we know anything about that? Will the adversary like make a pass with a magnet over your storage medium (in which case we might reasonably assume that contiguous blocks of data will be affected). A scheme based on an RS-code has the big plus side that with $R=B/r$ check symbols we can correct up to $R/2$ corrupted symbols. You can double this number, if (a big if, but again something I need to ask) we know the locations of the changes. – Jyrki Lahtonen May 24 2012 at 19:31

1

...(continue, sorry^2). How large can we expect M+B to be? Are we talking kilobytes, megabytes or gigabytes? At some point the granularity of RS-codes may become an issue. Another idea that comes to mind is to "waste" some of the storage space of the original copy by adding 32-bit CRCs to chunks of data (or some error-detection scheme like that). Then we can encode/decode on a chunk-by-chunk basis, and we shall automatically know which chunks are corrupted (in which case R extra chunks in B allow the recovery of R corrupted chunks in M). But again, a single flipped bit will ruin a chunk. – Jyrki Lahtonen May 24 2012 at 19:41

2

Without some restrictions on the backup, it seems to be a red herring. You want to be able to extract some number of bits out of $M$, a standard problem. If you can store $B$ bits reliably in the backup, this lowers the number of bits you need to store in the medium by $B$. – Douglas Zare May 24 2012 at 20:43

show 3 more comments

Partial backups

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.