AVR-Chat

On Mon, Mar 07, 2005 at 08:28:07AM -0600, Chuck Hackett wrote:

> In the ROBIN document, under "Multi-Master" you mention that, upon
> detection of a collision between two masters (both trying to send at
> once) the master should "back-off by a random amount".  I understand
> the concept, but, given two devices containing identical hardware,
> software and reset at the same time (i.e.: has the same "life
> history") how does it generate a random number with a high
> probability of being different from other devices?

One thing I had played with was letting one of the A/D lines float,
and use it's value for the seed.

Another alternative is to set one of the timers to free-run, then when
the first uart receive interrupt occurs, use the timer value at that
time for the seed.  Due to variations in the crystals, chances are
those counters won't be the same for any two boards except for very
high precision clock sources.

If one wanted to get really really good random number sequences, like
cryptographic quality randomness, another method would be to use a
radioactive source and detector.  Between any three detector hits, if
the time between the first to the second is greater than the second to
the third, call that a "1" bit, otherwise call it a "0" bit.  You'll
get some very seriously high quality random data that way, though the
effort might not be worth it in this application :-)

> My thoughts:

> 0) Can't use memory contents as a random number seed since the
>    devices history may be the same causing lockstep random numbers.

Right.

> 1) Pass the on-chip timer/clock value through a hash to generate
>    pseudo-random delay values that are widely dispersed given small
>    time value differences.  This assumes that the devices are not
>    running from the same clock and/or not reset by the same HW reset
>    signal.

Yep.

> 2) Use a value from an independent clock source such as an RTC as
>    the hash input in #1.  The problem here, again, is that it
>    doesn't work unless the RTCs are different and not in lockstep.

You could use the RTC to clock a certain duration and after that has
expired, take the value of a counter being clocked by the main system
clock.  Similarly to what I mentioned above, due to variations in
crystal clocks they don't clock with super high precision and after a
short time two crystal clocks will certainly diverge, providing
different seeds.

> So, if you don't have some independent random number seed source
> (independent clock, noisy diode, etc.) how do you generate the
> random/pseudo-random back-off delay?  Are there register/memory
> contents of an AVR that are truly "random" at power-up/reset and not
> dependent on the device's past history?

Not that I'm aware of.  I think you'd have to use some environmental
entity that you can measure, or use small variations in crystals, etc,
to provide different seed values for the pseudo random number
generator.

> Hmm, just thought of a #3: Use very high amplification on one of the
> internal A/D's to intentionally read "noise" and use the low byte as
> the random number or as the seed ...

Yes - similar to what I mentioned above.

-Brian
-- 
Brian Dean
BDMICRO - ATmega128 Based MAVRIC Controllers
http://www.bdmicro.com/