[BitTorrent] Re: Really random?

John Prevost j.prevost at gmail.com
Sun Jul 18 16:16:44 EDT 2004


On Sat, 17 Jul 2004 18:37:07 -0000, shad0wmatt3r <mgp at ucla.edu> wrote:
> Hi Arvid,
> 
> Quick question... Does this algorithm garuantee that by the
> time the nth piece comes in, that every piece received whose
> index is < n is in its correct (final) position on the hard
> drive? I'm interested in an efficient way to maintain this
> invariant.

I'm not Arvid, but yes it does.  Here's the algorithm, in a similar
form to yours:

*** BEGIN PYTHON CODE ***

from random import shuffle

def swap(piece1, piece2):
    global completed_file, piece_loc, loc_piece
    data1 = completed_file[piece1]
    data2 = completed_file[piece2]
    piece_num1 = loc_piece[piece1]
    piece_num2 = loc_piece[piece2]
    completed_file[piece1] = data2
    completed_file[piece2] = data1
    loc_piece[piece1] = piece_num2
    loc_piece[piece2] = piece_num1
    piece_loc[piece_num1] = piece2
    piece_loc[piece_num2] = piece1

def addToFile(next_piece_index, next_piece):
    global completed_file, piece_loc, loc_piece, pieces_completed
    global num_swaps, max_swaps

    cur_swaps = 0

    completed_file.append(next_piece)
    piece_loc[next_piece_index] = pieces_completed
    loc_piece[pieces_completed] = next_piece_index

    if next_piece_index < pieces_completed:
        swap(pieces_completed, next_piece_index)
        cur_swaps += 1

    if piece_loc[pieces_completed] != -1:
        swap(pieces_completed, piece_loc[pieces_completed])
        cur_swaps += 1

    pieces_completed += 1
    num_swaps += cur_swaps
    if cur_swaps > max_swaps: max_swaps = cur_swaps


initial_file = 'abcdefghijklmnopqrstuvwxyz'
piece_order = range(len(initial_file))
shuffle(piece_order)

completed_file = []
piece_loc = [-1] * len(initial_file)
loc_piece = [-1] * len(initial_file)
pieces_completed = 0

num_swaps = 0
max_swaps = 0

for next_piece_index in piece_order:
       addToFile(next_piece_index, initial_file[next_piece_index])

print 'completed file = ' + ''.join(completed_file)
print '# swaps = ', num_swaps
print 'max swaps = ', max_swaps

*** END PYTHON CODE ***

The primary difference with yours is that in order to make the
invariant hold, we need to keep track of both directions: we need to
know what piece is in a given location, and what location contains a
given piece.  piece_loc[x] is the location of piece x.  loc_piece[x]
is the piece in location x.

Every time we receive a piece, we write it at the end of the file. 
(I'm not sure exactly how the actual algorithm in question does this,
since individual blocks of data are also written to disk in random
order.  It could be that "every time we're going to request a new
piece, we allocate it at the end of the file and then do the rest of
this, instead of waiting for it to finish before swapping.)

Once that new piece is at the end of the file, we then say "should the
new piece be somewhere earlier in the file?  If so, swap it with
whatever piece is currently in that position."  Since we know that
every piece up to the current file position is in the right place, we
know that the piece we move is not yet in its right location, since
our new piece belongs there.

Now, after that first swap, we have a second question to ask: "Is
there a piece in the file that should be in our newly allocated
position?"  We look in the piece_loc mapping to ask "where is the
piece that belongs at the current position?"  If it exists, we swap it
with whatever is at the current position.  Again, since the invariant
holds, we know that if a piece exists that belongs at the current
position, then the piece there now does not belong in that position.

The big thing in this that looks more complicated is the function that
swaps two pieces: but all it really does is swap the data through temp
variables, and also swap around the piece_loc and loc_piece data. 
This is the place where both piece_loc and loc_piece are needed--we
only need piece_loc elsewhere, but here loc_piece is needed to adjust
piece_loc correctly for the swap.

There *are* more swaps later in the file, but never more than two
swaps per iteration, and never more than one swap per piece amortized
over the entire file.

Hope this is useful.

John.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list