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

Eric Gindrup gindrup at okway.okstate.edu
Tue Aug 26 12:52:51 EDT 1997


        I agree with your definition of tardy block.
     
        We know which blocks have been assigned since be know which 
     stretches of the keyspace have been sent out by proxies.  We can 
     roughly estimate how long ago a block was assigned from this 
     information.  We know a block is tardy if it is in a region that has 
     been assigned but that has not been reported as not containing the 
     target key.
        So right now our tardiness information would be sketchy, but not 
     meaningless.
     
        Actually, since blocks are assigned as wholes, we might want to 
     discuss what exactly it means to randomly generate a tardy block.  The 
     entire block will be checked, partially redundantly and partially not. 
      Further, since the amount of the *keyspace* checked is (x-y/2)%, the 
     "tardies first" method requires x-y/2 > y/2, or x>y.  "Randoms first" 
     requires x<y.
        I claim x >> y by looking at the proxy stats and comparing with the 
     completed keys stats.  The number of tardy blocks is pretty small.  In 
     fact, it is so small that the difference between y and y/2 is 
     negligible compared to x.
     
        I also wonder whether the assertion that a tardy block might be 
     returned is really valid.  The likelihood that a block will be 
     returned falls off pretty quickly after a, say, 8MHz 8086 would have 
     done the block.  My example was 150 days which is an inordinate amount 
     of time for a machine to do a block.
     
        Saying the "expectation of success is greater" is equivalent to 
     saying "the wastage of work is lower".  The expectation of success on 
     wasted work is zero.
     
        The number of allocated blocks (to the last time the executive 
     stats were updated is): 42214256.  So x = 15.7%.  The reported overall 
     copmletion rate is 874368kkeys/sec.  The proxy stats are, of course, 
     unavailable.  I would suspect that the proxies are assigning keys at a 
     rate very close to the overall completion rate.  In any event, assume 
     (very pessimistically) 10% of all assigned blocks will never be 
     returned.  Then y = 10% and x > y and so it is still better to work on 
     tardies before working on randoms.  The only way to change that is to 
     reduce the number of tardies or decrease the percentage completed.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: [rc5] Re: Tardy blocks (was Random keyblocks)
Author:  <rc5 at llamas.net> at SMTP
Date:    1997/08/26 10:40


At 08:56 AM 8/26/97 -0600, you wrote: 
[snip]
     
I don't think that the keyspace tracing information contains 
any time/date data so we are stuck with this. If the assigned 
keyspace database _does_ have dating info then we've got a lot
of choices. Realize that IF some form of an algorithm was used to 
allocate the blocks, IF our "tardy allocator" can follow the
same algorithm through the keyspace and re-allocate any of the 
un-checked blocks that it finds, then this counts as "history" or 
"date/time" info. Basically perfect for our situation.
     
>        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 
>...
>        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.
     
Actually if the "random" is truly random throughout the keyspace, 
then (x + y/2)% of the random block work is wasted. If we don't have 
any data on tardy-ness, then the y/2 figure will have to be modified 
because some of the assigned blocks will be returned. So it will be 
something like y/z% wasted effort on any tardy blocks, where z<2 and 
as we exhaust the keyspace and accumulate tardy blocks z -> 2.
     
>        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.
     
No, not because the expectation of success being greater, rather 
the waste-age of work is lower.
     
>  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 
     
How do you know? Perhaps y > 1/2? I have no data at all on the number 
of allocated blocks.
     
  Marc Sissom               | Design Engineer
  DNA Enterprises, Inc.     | Phone: 972/644-3301 
  269 W. Renner Parkway     | Fax: 972/644-6338 
  Richardson, Texas 75080   | http://www.dnaent.com
     
----
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