0
$\begingroup$

So i am at a LAN party where there are $n$ computers of which one $c_0$ computer has a file he wants everybody to have. Let's assume that transferring the file always takes $t$ time between any two computers.

Initially only the one $c_0$ computer has the file. He then transfers the file to a computer $c_1$ which takes $t$ time. Now there are 2 computers in the LAN that have the file. They then transfer the file to one new computer each, $c_2$ and $c_3$, which takes $t$ time. So after $2t$ time 4 computers have the file. And so in $xt$ time $2^x$ computers have the file.

How long does it take for a file that takes $t$ time to be transferred, to be distributed among all $n$ computers?

edit: What if only one-to-one transfers are allowed? E.g. two computers cannot 'work together' to transfer the file to one computer in $t/2$.

1 Answers 1

3

$t*log_2(n)$ time. Each transfer between two computers takes the same $t$ time, so we can assume that all transfers at a "stage" of the process happen concurrently. After each stage, double the number of computers as the last stage have the file (base-2 exponential growth), so the number of stages of transfers that must occur is logarithmically bound, base-2, to the number of computers in total that must have the file. As $log(1) = 0$ regardless of base, the operation is bound to the entire number of computers, even though one of them already has the file (and thus it would take 0 time for the trivial case of a group consisting of the one computer that already has the file). In computer-science lingo, this operation is logarithmic-time, or O(logN).

EDIT: From my comment, if $n$ is not an exact power of two, the logarithm will produce a decimal result. If the time $t$ required to transfer one file to one computer is a minimum bound, then the correct answer is the next higher integer value for the log, $t*ceil(log_2(n))$. However, if $t$ is the time it takes for one computer to transfer one file to one recipient, and it is possible in this system for $n$ computers to each transfer $1/n$ of the file to 1 recipient in $t/n$ time, then the decimal log value is correct, because for $n = 2^x+y < 2^{n+1}$, each of the $y$ computers can receive a fraction $y/2^x$ of the file from $2^x/y$ other machines, taking $ty/2^x$ additional time after $t*log(2^x)$, approaching the decimal value of $t*log_2(n)$. This is the ideal behavior of P2P systems like BitTorrent where every computer that has the file (or any portion of it) can re-distribute portions of it to any computer requesting the file, and thus the file's data can come from as many sources as are available, making the bound on transfer time the much larger download bandwidth of the average consumer internet connection and a fraction of $t$.

  • 0
    Thanks! But what about this scenario: there are 5 computers, after 2 steps 4 computers have the file, but now it takes a whole step to transfer the file to that one last computer, which gets to a total of 5 steps, instead of $log_2(5) = 2.32$. I guess i only want integers as answers? How can we take this into consideration?2012-08-14
  • 1
    Round up to the nearest integer. If there are $2^n+x$ computers where $x<2^n$, those x computers will take the full $t$ time to transfer, but only $x < 2^n$ computers that already have the file will be used during that stage. OR, in a system like BitTorrent, those last transfers could be accomplished by having all $2^n$ computers send a part of the file to the $x$ that don't, which may break the minimum bound of $t$ time to perform a transfer of the file to one computer.2012-08-14
  • 0
    oh... it's that simple? I feel stupid now! Thanks though :)2012-08-14
  • 0
    But wait... Shouldn't an ideal behavior for a P2P system like BitTorrent be that distributing a file among $n$ computers takes only $t$ time? We don't have to wait for the whole file to be transferred before sending it on to other computers. If each computer has as much upload as download bandwidth, and transferring the file between any two computers 'normally' takes $t$ time, then using BitTorrent it should ideally take the same time $t$ to transfer the file to all other computers as well. No?2012-08-14
  • 0
    Depends on what is causing the bound of $t$ time to transfer the file. The typical consumer internet connection is asynchronous; less upload than download, because that's what we do more of. So, in that case $t$ is bound to the upload bandwidth of one computer. But, if two computers with the same upload speed were each sending you half of the file, assuming the download speed of the recipient is at least twice the upload speed, you'd get the file in $t/2$ time. By increasing the number of uploaders per downloader, transfer time becomes bound by the much larger download bandwidth.2012-08-14
  • 0
    If upload and download bandwidths were synchronous, then transfer time would be fully constant regardless of the ratio of uploaders to downloaders, and the rounded-up value would be correct.2012-08-14
  • 0
    If i hack up the file in infinitely small pieces, they take an infinitely short time to transfer. Lets say the reciepents are people and i have them form a line, and feed the first in line with the infinitely small pieces which takes an infinitely short time for each transfer, and he then makes a copies of the pieces and hands them over to the next person, which takes an infinitely short time, and then that next person hands them over to the person after him and so on. Distributing the file to all $n$ persons now takes an infinitely short time? No? Hmmm...2012-08-14
  • 0
    Sorry I'm just talking nonsense. Im going to bed now.2012-08-14
  • 0
    No, because $1/n * n == 1$ as $n \to \infty$; if there is a maximum download bandwidth defining the minimum bound $t$, then that is a lower bound regardless of how many different senders there are or how small the chunks are.2012-08-14