tomasz has asked for the wisdom of the Perl Monks concerning the following question:

I have a problem I've been trying to solve, but must be too weak for it mathematically. Here it is.

In the standard download procedure, the server sends the file down to the client, either in it's normal, literal state, or compressed. Now, what if I want to push the downlink load even further down (1)? As the server, I'd rather have the client be more active asking me questions, limiting myself to as few and as short answers as possible. So I'm trading server (2) network down-link transfer for computation on both ends. And the question is: what are the optimum points here?

Certainly the absolute minimum would be for the server to have all possible values sent up to it and then just answer yes once, when the right question arrives, leaving all the wrong values unanswered - assuming reliable network transfer and some decisive timeout. But what other options are there?

My edits are in bold with edit numbers in brackets next to them.

Replies are listed 'Best First'.
Re: Reverse download protocols
by jdporter (Chancellor) on Aug 30, 2021 at 15:01 UTC

    I'm having trouble understanding your terminology. When you say you want to "push the downlink load even further", do you mean you want to reduce the downlink bandwidth requirement even further? e.g. reduce the downloaded file size more?

    I'm not sure, but my guess is that the solution is probably rather domain dependent, and in particular depends on how much a priori knowledge is shared by both client and server. Any chunk of information that is already known to both could be "compressed" as a single short datum (e.g. UUID). For example - if the data being downloaded is always similar (e.g. genome sequence data, or astronomic imagery), then you could potentially always use the same dictionary, or set of dictionaries, for compression; then store those dictionaries on both client and server and not download it.

    Is there a "sweet spot" for this? Not that I know of. You might have to determine one for your specific scenario statistically.

    I reckon we are the only monastery ever to have a dungeon staffed with 16,000 zombies.
      Of course reduction of down link is what I meant - corrected for you.

      And no shared information can be assumed. Think of it as operating on a popular download server, where the file to be downloaded can be anything.

        Can you explain what you mean by "questions" and "answers", and how those would affect the download?

Re: Reverse download protocols
by bliako (Monsignor) on Aug 30, 2021 at 18:27 UTC

    There's the 20-questions game of: client trying to guess a server-chosen integer. The server responds with one of higher, lower or yes to any guess from the client. The best strategy for such a game is to always guess halfway between the current possible range. This is because you are essentially doing a binary search and want to eliminate the biggest possible range with your every question, slowly zooming-in to the correct answer.

    The output of a hashing algorithm can be labelled as a unique non-negative integer (or be converted to one). SHA1 has 160 bits of output. Giving the possible guesses to be in the range 0 to 2^160 = 0 to 1461501637330902918203684832716283019655932542976. The best guess would be 2^160/2. If the server answers with try lower, then your next guess should be 2^160/4.

    Bonus points for how many guesses guessing a SHA1 hash needs, given that the server is ever so helpful in giving us 2 bits of information each time. But from what I gather from this post's little 20-questions game, the server does give hints (e.g. Then the server answers yes/no, or gives some hint.)

    Here is something to play with, if indeed your problem falls in this category (it certainly did keep me entertained for a while):

    # by bliako on 30/08/2021 # for use bigint qw/hex/; use Digest::SHA1 qw/sha1 sha1_hex/; my $digest_hex = sha1_hex('blah blah blah'); my $answer = hex($digest_hex); print "$0 : starting with this number: $answer.\n"; my $min = 0; my $max = 2**160; my $num_guesses = 0; my ($guess, $diff); while( ++$num_guesses ){ $guess = $min + ($max - $min) / 2.0; $diff = $guess - $answer; print "entering at guess number $num_guesses, current range:\n mi +n: $min\n max: $max\n answer: $answer\n guess: $guess\n diff: $di +ff\n"; if( $guess < $answer ){ print "your guess ($guess) needs to go higher ...\n"; $min = int($guess); } elsif( $guess > $answer ){ print "your guess ($guess) needs to go lower ...\n"; $max = int($guess); } else { print "bingo in $num_guesses guesses! the answer was: $digest_ +hex and your guess was ".bigint_to_hex($guess)." ($guess).\n"; last; } } sub bigint_to_hex { # graduitously ripped off from Ben Aveling's answer in # +-a-big-number-in-perl # because sprintf("%x", bigint) does not work sadly... my $inp = shift; my $out = ""; while($inp){ my $chunk=$inp & 0xf; $inp >>= 4; $out = sprintf("%x",$chunk).$out; } return $out; }
    entering at guess number XXX, current range: min: 216530321997656745029789011476757518019484653536 max: 216530321997656745029789011476757518019484653568 answer: 216530321997656745029789011476757518019484653552 guess: 216530321997656745029789011476757518019484653552 diff: 0 bingo in XXX guesses! the answer was: 25ed8e31b995bb927966616df2a42b97 +9a2717f0 and your guess was 25ed8e31b995bb927966616df2a42b979a2717f0 +(216530321997656745029789011476757518019484653552).

    EDIT: this is interesting reading

    bw, bliako

      Thanks a lot for your positive reply. I will give you feedback later on. I need to analyse your thoughts. It may take a while... It's not exactly what I asked about, but closely related. Thanks again!
    A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Reverse download protocols
by salva (Canon) on Aug 31, 2021 at 12:59 UTC
    Unless you have some shared information, you can not reduce the number of bits that need to be transferred. It can be easily proved because it is equivalent to the Pigeon Principle.
Re: Reverse download protocols
by The Perlman (Scribe) on Aug 30, 2021 at 19:57 UTC
    This reminds me of authentication protocols in cryptology, where the one-way-encryption keys are never exchanged.

    A sends a sequence of random values and B must reply with the correct encryption or just a property of it. After n correct answers A will be statistically "convinced" that B had the correct key.

    Because of the asymmetric nature the correct key can't be deduced by a listener in the middle.

    I doubt it helps, but the question allows so many wild interpretations...

    - Ron
      I don't know how what you describe works in cryptology, but that's definitely the vibe here. Something like an intersection of a series of "hashes". The art here is to find out the method of building them.
        > Something like an intersection of a series of "hashes".

        It would help to know for which reason.

        There is no way this will be more performant than a direct download.

        Anyway anything which will work "your way" on a string will also work on a serialized hash. Just use Data::Dumper to get your string.

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery

Re: Reverse download protocols
by LanX (Sage) on Aug 31, 2021 at 13:40 UTC
Re: Reverse download protocols
by Perlbotics (Bishop) on Aug 31, 2021 at 18:06 UTC

    Just something to complete this insanity:

    sub steal_a_file_from_our_isp_that_charges_for_downstream_net_bytes_on +ly { my ($some_kind_of_uri) = @_; my @buffer; my $location = 0; while ( 'true' ) { my $done = 0; for my $val (0..255) { #-- 0..255: use a list with values sorted by highest probability # first for an incredible speed boost my $resp = query_server_if_byte_at_location_has_value($some_kin +d_of_uri, $location++, $val); next if $resp eq 'timeout'; return @buffer if $resp eq 'eof'; push @buffer, $val; $done=1; last; } $location-- unless $done; # 256 timeouts, so the response was lost + and we need to retry } }

    A reply falls below the community's threshold of quality. You may see it by logging in.
A reply falls below the community's threshold of quality. You may see it by logging in.
A reply falls below the community's threshold of quality. You may see it by logging in.
A reply falls below the community's threshold of quality. You may see it by logging in.