Timeline for Partial backups
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27, 2014 at 5:40 | vote | accept | Matthias Goergens | ||
| Oct 24, 2013 at 1:55 | answer | added | Yuichiro Fujiwara | timeline score: 2 | |
| May 29, 2012 at 17:40 | comment | added | Matthias Goergens | Jykri, as for the adversary model, one scenario I had in mind was: a company wants to offer an online back up / restore service to customers. With a complete backup you'd have to wait for a full initial upload before the backup becomes useful. But with an (extensible) partial backup scheme, you can revert some changes to the initial data right away. (To keep the scheme simple at this point, we disallow changes halfway into the upload.) | |
| May 29, 2012 at 17:32 | comment | added | Matthias Goergens | Douglas, that's the result I want to achieve eventually. But I don't see what kind of systematic code would do that. Also in the case of very small B's I don't see how that would work. Correcting a single bit error/change in M requires more than a single bit in B, because you are essentially encoding the position of the flipped bit, which needs log M space. | |
| May 25, 2012 at 4:36 | comment | added | Jyrki Lahtonen | I quite like Douglas Zare's thinking. But if using RS-codes it won't increase the number of correctable errors (well, may be marginally, if it allows the use of symbols shorter by one bit). | |
| May 24, 2012 at 20:43 | comment | added | Douglas Zare | 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$. | |
| May 24, 2012 at 19:41 | comment | added | Jyrki Lahtonen | ...(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. | |
| May 24, 2012 at 19:31 | comment | added | Jyrki Lahtonen | ...(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. | |
| May 24, 2012 at 19:25 | comment | added | Jyrki Lahtonen | 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. | |
| May 24, 2012 at 18:31 | comment | added | Andreas Blass | 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.) | |
| May 24, 2012 at 18:11 | history | asked | Matthias Goergens | CC BY-SA 3.0 |