[rc5] Random keyblocks
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
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
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
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
> 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
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5