[MUD-Dev] Re: [DevMUD] Re: Database module

[cynbe at muq.org]

-----BEGIN PGP SIGNED MESSAGE-----


On 22-Dec-98 J C Lawrence wrote:
> Within very large values of "TRUE" there are no truly random number
> generators.  Yes, there are some, just not many (ie I'd wager not from
> from 1,000 on the planet, total).  (cf LavaRand at
> http://lavarand.sgi.com/ -- I work with some of the guys that did
> LavaRand BTW).
> 
>> It is often practical to make this long enough to make collision
>> probability effectively zero for the purposes at hand.  
> 
> Unfrotunately approximately zero is never quite the same as zero.

But we live in a probabilitistic universe, no?  There's some chance
all the hydrogen in my body will fuse into helium a microsecond from
now:  Just requires some improbable but permitted quantum tunnelling.
I don't lose sleep over it, 'cause the probability is effectively
zero for all practical purposes.

I see nothing wrong with probablistic hacks as long as the expected
failure rate due to them is a small fraction of the overall expected
failure rate of the system.
 
> Ahem.  Not quite true.  They may have damned good PRNG's, very well
> tested, graphed, measured, and expertly coded PRNG's with well
> documented behaviours and caveats, but they are very definitely
> Pseudo-RNG's.

Perhaps we're using different definitions of PRNG here.

PGP uses irregularities in human typing speed as a source of entropy.
Whether that is "truly" random may depend on your philisophical stance
on free will, the foundations of quantum mechanics &tc.  But I think
we can agree a practical exploit depending on the ability to predict
such variations isn't a practical prospect this decade?

Another approach I've seen keys off the fluctuations in rotational
velocity of hard disk drives:  I'm told that whereas head seek times
are pretty deterministic, rotational flutter is dominated by turbulence
around the disk head, which is an example of physical chaos.  Again, you
may subscribe to a physical model which makes such chaos "deterministic",
but I think we can agree that practical exploits are a long way off.

For Muq, I'm not making any great claims to analysis of phsical systems:
I just XOR the microsecond-precise time of arrival of events like network
packets and disk reads into an internal buffer on a continuing basis as
the system runs.  When I need some "truly random bits", I just SHA-1 hash
the buffer and return it.  That's not very formal (e.g., I don't meter the
entropy in vs entropy out to ensure that the former exceeds the latter), but
I'd be quite surprised if that turned out to be the biggest weakness in the
muqnet distributed authentication and encryption layer.

> 
> Why go for a PRN, especially when its a time bomb waiting to happen
> that you can't predict, can't detect when it doesn happen, and can't
> (usefully or elegantly) handle the effects of when it does blow up?
> Yes, its bloody rare, I'm just not fond of that sort of thing,
> especially when I have an alternative and a guaranteed correct one at
> that (assuming system time is reliable (Kanga.Nu is NTP stratum 3
> right now, soon to be stratum 2 if I have my way)).

Possibly in the specific case at hand, no reason at all!

But I think it is clear that in general, randomness is a great help
in distributed algorithms, primarily as a cheap way of discoordinating
different branches of the effort without using a central mechanism
which can be both a single point of failure and a performance
bottleneck.

E.g., without randomness, PGP would produce the same public keys for
everyone, so we'd have to depend on a single central authority to issue
all public/private keypairs, raising issues of trust and reliability and
such.

E.g., with your time_t approach on a multiprocessor machine, you'll need
to keep a unique numbering of each thread in the system and combine that
with the current time value, I think, in order to guarantee uniqueness?
Which might start becoming a significant pain on a 512-node Beowulf cluster,
say.  

But I'm sure you knew all that.

(Or do you never use hash tables? :)

  Cynbe


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3a
Charset: noconv

iQCVAwUBNn+K4j35srNZ3GptAQES6QP/U0rE0Y3qgFUpOXP1yMHUkdyJcsTmQQgc
/0qgTZciJ3JvDaUwlm4+9aTsLnFOJLoalJ79X2L/YLMbxNja2zIq1IT7Ci+3j3XF
XjhbJdiOQK1E0p6C0icPxPoTxx130AYdPpDmxd0Rr/WxCUevv2x2BZkrsjyqJEen
V7d75UjnOLA=
=tmhH
-----END PGP SIGNATURE-----