4 ms·
My favorite example of an impossibility theorem being violated in practice is rsync. The theorem being that there is no perfectly reliable algorithm to compare
by btilly 6y ago
My favorite example of an impossibility theorem being violated in practice is rsync.
The theorem being that there is no perfectly reliable algorithm to compare two files across a network and see if they are different that in the worst case does not require at least as much bandwidth as transferring one file to the other.
Lots of algorithms do better on most files we see. For example compress and send a compressed file. But in the worst case, the compressed file can be larger than the original and you have to transfer it.
Enter the rsync algorithm. It sends a tiny amount of data. Just a hash. The gotcha is that it has a very small chance of incorrectly concluding that two files are the same. But the odds that it gets it wrong are in practice lower than the odds of it getting it wrong because of a hardware failure during the computation. (The algorithm continues doing more hashes to narrow down to just the differences if the file needs to be updated.)
- lambdatronics 6y agoYou make in interesting point. Much of algorithmic information theory seems to be focused on the worst case, when the average behavior may be more relevant -- and significantly more pleasant. It brings to mind Zipf's law and optimal coding. There's a 'no-free-lunch' theorem waiting to be discovered, I suspect -- or maybe it already exists and I just haven't heard of it. Something along the lines that optimal encoding maximizes the channel capacity, but makes the worst case error exponentially disastrous.
- kobalsky 6y agoI think it's good to clarify that rsync's algorithm requires an agent on the remote computer to compute those hashes without sending the file over the network.