[rc5] Re: Tardy blocks (was Random keyblocks)
gindrup at okway.okstate.edu
Tue Aug 26 09:56:58 EDT 1997
I haven't really been discussing handing out tardy blocks instead
of handing out unassigned blocks. I've been suggesting tardy blocks
instead of random blocks, with a lot of little details and caveats.
So to take your analysis into the picture. Say x% of the keyspace
is checked. y% of the blocks are tardy. there is no chance that the
solution key if found in a tardy block would never be reported by the
client that found it (Strictly, this is wrong, but the correct
probability of non-reporting is negligible.), all tardy blocks are
caused by crashes (or some other event that interrupts the check in
the middle of a block run), and that the point of interruption is
distributed uniformly throughout the tardy blocks. (This last isn't a
very good assumption, but I have no model to suggest a reasonable
From our assumption of uniform distribution, we can derive that (on
average) 50% of each tardy block has been checked. So y/2% of the
keyspace has been assigned but not checked. So x% of all work on
random blocks is useless and y/2% of all work on tardy blocks is
Therefore, if x > y/2, then it is better to work on tardy blocks
than to work on random blocks since the expectation of success is
greater. Conversely, if x < y/2, it is better to work on random
blocks (since so little of the keyspace has been checked).
Now, for the current effort, x is much greater than y > y/2, so it
is better to work on tardy blocks. Of course, no work is wasted on an
unassigned block, so the proper priority scheme for working on blocks
is: unassigned, tardy, random. If 2/3 or more of assigned blocks were
tardy, then the proper scheme would be: unassigned, random, tardy.
I would never claim that it is more likely that the solution is in
a tardy block than in an unassigned block until the number of tardy
blocks is twice the number of unassigned blocks (by an analysis
similar to the above -- if more than twice as many blocks are tardy
than unassigned, then more of the unchecked keyspace is in tardy
blocks than in unassigned blocks...) Therefore, as the keyspace
becomes exhausted, the greater expectation of effectiveness is to
assign more tardy blocks than unassigned blocks.
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: [rc5] Re: Tardy blocks (was Random keyblocks)
Author: <rc5 at llamas.net> at SMTP
Date: 1997/08/26 04:03
At 03:16 PM 8/25/97 -0600, Eric Gindrup wrote:
>> 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.
In fact, "tardy" blocks have *less* probability of containing the solution
key because many of the tardy blocks caused by computers crashing in the
middle of a block. This means that if they crashed while processing a
block, then a solution had not yet been found in that block (because if it
had, the block would have been stopped there and the solution-notification
written to the buff-out). And since we have not yet received any legitmate
solution notfications, well.. make your own conclusion.
Even if you assume that only a very small percentage of the "tardy" blocks
became lost because of a mid-block crash, that small percentage still makes
it more probable that a block that hadn't been distributed at all before
will contain the solution key.
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5