Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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? –  Pärserk Aug 14 '12 at 20:36
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. –  KeithS Aug 14 '12 at 20:38
    
oh... it's that simple? I feel stupid now! Thanks though :) –  Pärserk Aug 14 '12 at 20:43
    
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? –  Pärserk Aug 14 '12 at 21:08
    
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. –  KeithS Aug 14 '12 at 21:14
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.