[rc5] Random keyblocks

Eric Gindrup gindrup at okway.okstate.edu
Mon Aug 25 16:16:58 EDT 1997


        Actually, these questions intentionally are in the order they are 
     in.  At some point, the assertion that a tardy block has no more 
     chance than a *randomly generated* block is false.  That it has no 
     more chance than the next one in the hand-out queue is certainly true.
        Eventually, though, the redundancy of rechecking caused by randomly 
     checking blocks eliminates any benefit from randomly generating 
     blocks.
     
        Your stack comment would make the handing out of tardy blocks even 
     easier.  Tardy blocks could be handed out, oh, I dunno', .01% of the 
     time that a client requests a new block.  Since blocks that have been 
     tardy for the past 150 days are, realistically, not very likely to be 
     completed any time soon, having the speedy clients (the ones that 
     report blocks often enough that they actually receive tardy blocks) 
     work on tardy blocks instead of random blocks guarantees that less 
     work is wasted when the keyspace has been more fully explored.
        Since the architecture is a stack, the tardy blocks could be 
     assigned to be at the bottom of the stack.  In which case, the request 
     for a new block would need to fail (this might actually simplify some 
     of the in-buff handling code) before the tardy block would be picked 
     up and examined.  Then when the tardy blocksat the client were 
     exhausted, random blocks could be generated.
     
        A rational system of reassigning tardy blocks would assign them 
     more frequently as the keyspace was exhausted.  This is no different 
     from the information in the FAQ that tardy blocks will be declared 
     "lost" when all the blocks have been assigned out at least once and 
     then the second pass will consist of only those blocks not completed 
     in the first pass.  In this scenario, though, more and more work is 
     wasted on random blocks as the keyspace becomes exhausted.
     
        Imagine that we have 1% of the keyspace exhausted.  1% of the time 
     a random block is useless.  A tardy block is almost never useless 
     because 1) it has not been determined that the tardy block does not 
     contain the key (which is not true for a redundant random block), and 
     2) the likelihood that it will be completed twice vanishes as the 
     tardiness increases.
        Further, completing tardy blocks could be used to increase the 
     effectiveness of random blocks by putting a lower limit on the range 
     from which random blocks were generated.  This would, of course, 
     reqire that blocks be assigned somewhat sequentially so that the 
     unassigned blocks were in some simply described region of the 
     keyspace.
        But we're not at 1%.  We're at 15.7%, so 1 random block in 6.4 is 
     wasted.  Eventually we'll be at 80%.  Then 4 random blocks in 5 will 
     be wasted.  I'd really rather accelerate the completion of the 
     keyspace search than increase the wasted effort.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu
     
     [snip]
     
> Would it be equally valuable to "pass out" tardy blocks to be 
> handled by detached clients?
     
Tardy blocks?  If you mean blocks that have been checked out for 
a long time, then no, not really.  A block that has been checked 
out, but never reported back has no more chance to be "the" block 
than the next one in the hand-out queue.
     
Bovine's cordinators have stated that if/when the entire keyspace 
has been handed out, that they'll start going through the blocks 
that haven't been reported back.
     
> At what completion percentage would it be more productive to
> start handing out tardy blocks instead of producing random blocks?
     
Don't know if it would really matter.  Especially with the 
buff-in.rc5 files working as a stack rather than a queue.  IE
"Oh, I've only got 5 blocks left in my buffer."  Update, and repeat. 
Those 5 blocks don't get worked on, at least untill the keyspace
is exausted.


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



More information about the rc5 mailing list