Date: 01/20/05 (Algorithms)    Keywords: no keywords

Consider two computers connected by a very asymmetric communications system. This means that download is far faster than upload from the POV of one of the computers (from the other, of course, upload is far faster than download).

Then, if A is the one whose upload is slow, and B is the one whose download is slow, is there any way for A, through receiving data from B and adapting, to "upload" a file (give B all of its data) quicker than the nominal upload speed of the line it is connected to, even if the data itself is random (or optimally compressed)?

I know that by the pigeonhole principle, it's impossible to upload faster than the nominal upload speed if B doesn't do anything but receive (or responds with the exact same messages no matter what data is sent). But is it possible to upload faster if B is active within the protocol?

(Perhaps B could rapidly upload combinations, and A would trigger with an acknowledgement when it received the right few next bytes? But even if we had zero latency, this would be slow as we'd have to wait on average until half of the possible combinations were uploaded by B before getting the right one. In extreme conditions, this still might be faster than A uploading directly, but can we do better? What if the connection is lagged?)

Source: http://www.livejournal.com/community/algorithms/44641.html