[RC5] Active subspaces/random subspaces

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Thu May 7 12:42:00 EDT 1998

     What I don't see, however, is how the problem you mention last will 
     ever go away...
     The current trend is to make even subspaces "official" and odd 
     subspaces "random".  You say that the clients are wired to make the 
     subspace after the official subspace the random subspace.  This 
     problem with the clients choosing random blocks out of a completed 
     subspace when the random subspaces are reissued doesn't go away 
     without recoding the clients.
     A better idea would be to abort 0x68 as an official subspace right 
     now, finish 0x64, make 0x65 official (causing some duplication in 
     0x66), reassign tardy blocks in 0x66, make ox67 official, and so 
     Skipping the random segments is going to cause a great deal of 
     random block duplication when half of the subspaces are completed.  
     I.e. *all* random blocks will be duplicates.
     Making the random segment be the next official segment reduces the 
     duplicate block rate somewhat since only clients which have not been 
     able to fetch since the subspace was incremented will be producing 
     possible duplicates.  The probability that a random block will be 
     duplicated increases the longer this noncommunicating interval 
     lasts.  The probability that an assigned block will coincide with a 
     random block that is reported first is proportional to the 
     percentage of blocks that will be generated by noncommunicating 
     clients at the time the block is assigned.  I would expect the 
     distribution of this percenteage to be roughly "exponential" based 
     solely on the shape of the RC5 keyrate graph after DES-II started.
     Crunching through all the math shows that there is more duplicated 
     effort if all the even subspaces are assigned, then the odd 
     subspaces are assigned, and the clients always pick random blocks 
     out of the "next" subspace.
     Similarly, there is less duplicated effort if the subspaces are 
     assigned somewhat sequentially so that only the last subspace in a 
     sequence of subspaces might immediately precede a complete subspace.
     The ideal solution would be to have the server protocol indicate 
     exactly which subspaces are random instead of that subspace being 
     implicitly defined by the fetched block.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu

______________________________ Reply Separator _________________________________
Subject: Re: [RC5] Active subspaces/random subspaces 
Author:  <rc5 at llamas.net> at SMTP
Date:    5/6/98 11:45 AM

The basic reason for this is that the clients are coded to use the current 
subspace+1 as the random subspace. It might be more space efficient to 
issue out of random keyspaces (ie: switch from 0x64 to 0x65, instead of 
0x66), but it would also increase the dupe rate durring switchover 
periods. Also, redoing random subspaces right now isn't an option, since 
that would make a completed subspace the random one, meaning that almost 
all randomly generated blocks would be dupes.
          /^\             Jim C. Nasby (aka Decibel!)
        /     \           nasbjim at charlie.acc.iit.edu
      /----+----\         Freelance lighting designer and database developer
    /      |      \       Member:
   +-------+-------+      Sports Car Club of America, Triangle Fraternity
On Tue, 5 May 1998, Richard Ellis wrote:
> > Stats on the current status of the subspaces are available at
> > www.distributed.net/statistics/graphs. The odd numbered subspaces 
> > are the random ones, and as you can see they are very empty.
> May I ask why, if we can only hold a total of four active subspaces 
> on the master key server, that we have two active random subspaces
> open.  Half of the active keys that could be handed out are not being 
> handed out because they are allocated to "random" subspaces.  Given
> the present space constraints on the master key server, it would seem 
> to make more sense to only have a single active random subspace. 
> This would allow for three quarters of the total available space on 
> the master to be allocated to active subspaces, lengthening the time 
> between subspace redistributions.
> Rich
> -- 
> Microsoft is not the answer.            Boycott Microsoft Home page 
> Microsoft is the question.              http://www0.vcnet.com/bms
> No is the answer.
> Microsoft: Bringing you ten-year old technology, tomorrow, maybe. 
> --
> To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net 
> rc5-digest subscribers replace rc5 with rc5-digest
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net 
rc5-digest subscribers replace rc5 with rc5-digest

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list