[rc5] Random keyblocks

Brian Foddy bkfoddy at skypoint.com
Tue Aug 26 19:18:55 EDT 1997

On Tue, 26 Aug 97 08:33:19 -0600, Eric Gindrup wrote:

>        Perhaps better would be to hash the "block-space" so that the 
>     hashed sequence of blocks would be random enough to wander all over 
>     the keyspace.  Then percentages completed could be reported with 
>     incoming blocks to the client.  So a random block could be generated 
>     from the last x% of the hashed keyspace where x is the unchecked 
>     percentage.
>        There would always be some marginal percentage that a random block 
>     was wasted, but that percentage could be controlled by limiting the 
>     interval from which the proxies are assigning blocks under the 
>     assumption that the percentage complete indicator is updated 
>     occasionally at the client.
>        Also, clients aren't expected to connect to get tardy blocks.  
>     Tardy blocks are expected to be assigned infrequently with a regular 
>     block.  So, if that client ever can't connect to get more blocks, it 
>     runs through its tardy blocks (or, equivalently, "highly useful 
>     'random' blocks") and then generates random blocks until it can report 
>     all completed work to a proxy.
>        The overhead of transmitting or storing the occasional tardy block 
>     is very low.  Furthermore, if one were concerned that a fast client 
>     with a reliable connection were to collect too many tardy blocks, then 
>     perhaps the client should have (yet another) option to limit the 
>     number of tardy blocks that it will collect.  Either it can work on 
>     them when the tardy limit is reached, or it can refuse to accept new 
>     tardy blocks.  A refused tardy block would just become tardy again and 
>     be reassigned to someone else.
>        The idea is that tardy blocks are assigned when the connection to 
>     the proxy is working and are only worked on when that connection is 
>     bad.  This increases the utility of the offline work over that of 
>     purely random block generation.
>        Finally, the only reason I can see for supporting purely random 
>     block generation is concern that clients are improperly reporting 
>     completion of blocks.  Perhaps a rogue client or some such is 
>     misreporting block completions.  The random blocks would thus serve as 
>     a check that reported blocks actually don't contain the desired key.  
>     Simplicity of coding is also an issue in random block generation, but 
>     the simplest design is just to exit.
>            -- Eric Gindrup ! gindrup at Okway.okstate.edu
What is the point?  Lets take an extreme example...

Suppose I download ALL remaining blocks, so I'm nearly guarenteed to
to have the solution somewhere.  But on a single P100 it might take me 
100 years to find the right block.  Then that makes all remaining blocks
tardy for up to 100 years.  Obviously, the contest wont wait, so...

By our current and stated policy, they will simply recycle the process
and start re-issueing tardy blocks.  So now, at least two computers
have the correct block in their buff-in.rc5 file.  Plain and simply, the
first of those two machines to process the right block wins.

In this extreme example, the odds and the time to solution HAVE NOT CHANGED,
assuming I still upload completed blocks periodicaly so no duplicate
work is done.  That is the main key, NO DUPLICATE WORK.  And since
it will likely take us many more months before we start recycling our
blocks the odds of any duplicate work is NILL.

Now back to reality...  Even if 10% of all blocks are never reported
the first go-around (a number that could be close to accurate), it doesn't
matter as long as nobody actually processes those 10% blocks but never
reports them, then its a waste.  But even in that case, its probably safe
to assume that machine will NEVER report any blocks again, so its as if
that machine never joined at all.  It all just means we will reach the
re-cycle point that much faster and then re-issue those blocks.

So in summary, as long as you get your blocks reported before they
recycle the blocks there is no penality or loss.  And that will
probably take months....  And if they are never reported, OH WELL.

Its all in the probabilities, and those rules state:

Just my 2 cents worth.
Brian Foddy
bkfoddy at skypoint.com
Eagan, MN  USA

To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.

More information about the rc5 mailing list