[BitTorrent] Re: Really random?

shad0wmatt3r mgp at ucla.edu
Sat Jul 17 14:37:07 EDT 2004

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.

The simplest algorithm I could come up with that doesn't pre-allocate
the entire file before downloading and sorts as the file as it is
written follows below. It does not, however, adhere to the invariant
mentioned above -- on the average, it tends to do more sorting as the
file nears completion.


from random import shuffle

def addToFile(next_piece_index, next_piece):
	global completed_file, piece_map, pieces_completed, max_shifts

	while next_piece_index < pieces_completed:
		old_piece_index = piece_map[next_piece_index]
		old_piece = completed_file[next_piece_index]
		piece_map[next_piece_index] = next_piece_index
		completed_file[next_piece_index] = next_piece
		next_piece_index = old_piece_index
		next_piece = old_piece
	piece_map[pieces_completed] = next_piece_index
	pieces_completed += 1

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

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

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

print 'completed file = ' + ''.join(completed_file)


Note that the "file" is just the string 'abcdefghijklmnopqrstuvwxyz',
where each letter represents a piece.


> This is, roughly, the algorithm I employ in libtorrent, I'm pretty
> it's the same for all clients supporting this kind of storage.
> storing a piece:
> 1. let A be a newly downloaded piece, with index n
> 2. let s be the number of slots allocated in the file we're
>     downloading to. (the number of pieces it has room for)
> 3. if n >= s then allocate a new slot and put the piece there
> 4. if n < s then allocate a new slot, move the data at
>     slot n to the new slot and put A in slot n
> allocating a new slot:
> 1. if there's an unassigned slot (a slot that doesn't
>     contain any piece), return that slot index.
> 2. append the new slot at the end of the file
> 3. let i be the index of newly allocated slot
> 4. if we have downloaded piece index i already (to slot j) then
> 4.1. move the data at slot j to slot i
> 4.2. return slot index j as the newly allocated free slot
> 5. return i as the newly allocated slot
> I wrote this from the top of my head, I may very well have
> something, feel free to correct any mistakes.
> --
> Arvid Norberg

------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!

Yahoo! Groups Links

<*> To visit your group on the web, go to:

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

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list