[rc5] Re: Tardy blocks (was Random keyblocks)

Eric Gindrup 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 
     alternative.)
        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 
     useless.
        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.
     
     
Jeff
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
     


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



More information about the rc5 mailing list