[RC5] [suggest] Control + Clients

Neil Duffee No.Junk.E-mail.to.Neil.Duffee at sympatico.ca
Sun Nov 14 11:34:39 EST 1999

This suggestion though more aimed at the Control category also
overlaps into the Clients.

There has been often-voiced concern about the client chosing random
blocks (after it has run out of those assigned by the server) that
might already have been submitted by another.  Likewise, others have
suggested changes to the search order used in a vain attempt to more
rapidly find the needle in the haystack.  I too am suggesting a change
to the order that blocks are assigned but aimed at the former
(perceived) complaint.

First, a little background (that you all know already but to give us
an equal starting point for *this* discussion).  Blocks are assigned
by the servers from a larger grouping of blocks (I don't recall the
proper terminology used by D.net);  call it an address space.  When an
individual client runs out of assigned blocks ie. an empty buff-in.rc5
file, for any multitude of reasons, it currently jumps to some random
point in the next address space and begins crunching merrily from
there until it is able to connect for more, properly assigned blocks. 
This is actually a good plan since each address space is sufficiently
large that chances of picking the same starting point in the secondary
address space approaches zero.  However, it is still work outside of
the primary space.

I believe that, within the current mixed environment of clients, the
server(s) should be handing out blocks (from the current address
space) in a binary search pattern rather than the current sequential,
beginning-to-end order.  To be precise, the first client gets blocks
starting at the middle of the address space, the next, from a position
0.25 from the beginning, the next, at 0.75, etc.  We all know what
wonders this brings to sorting algorithms.  The difference would come
when a client runs out of blocks.  Instead of jumping ahead to the
secondary address space, it would continue merrily on with the next
block in its list.  This change would continue to support the existing
client base since old clients would continue to jump to the secondary
address space for their random blocks.

Even with the 100's of thousands of clients running, the address space
is sufficiently large that collisions are likely small.  Except, of
course, when nearing the close of a particular address space.  To
combat this particular problem, the server might detect that it's
dealing with the new client and supply an ending point stating where
the next group of completed blocks begins.  Should the client reach
that point, it would jump to the *same* starting point in the
secondary address space.  Essentially the pseudo-randomness has been
provided by the server when it assigned the original block.

I can envision a problem that the client does not know where it
started since that last connection with the server and cannot jump to
the starting point in the secondary address space.  Perhaps the answer
would be to have the client work its way in the opposite direction? 
How would the client know that it's even *in* the 'alternate
universe'?  (where time runs backwards... *grin*)  It might read back
its buff-out.rc5 file but that could lead to circular logic. 
Likewise, it would hinder those who are running multiple clients from
a single set of buffers.  Perhaps the starting point in the secondary
space would be at the starting point of the next group of completed
blocks.  Since the blocks have been returned to the server, it is not
likely that some client has attacked them in the secondary space. 
(Definitely makes life easier for the client;  no alternate universe,
back 'n' forth, re-reading buffers, to deal with...)

In conclusion, this change will *not* help find the keys faster but it
*might* speed up the conclusion of a given address space as both
assigned and random block work are lumped together.  ciao.

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list