[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