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
    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