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

Marc Sissom msissom at dnaent.com
Tue Aug 26 11:40:31 EDT 1997

At 08:56 AM 8/26/97 -0600, you wrote:
>        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.

Nice thread. We need to work on the definition of "tardy".
Is this the def?

  tardy = assigned but not returned

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.

More information about the rc5 mailing list