On Tue, Feb 04, 2003 at 03:46:22PM -0500, Wietse Venema wrote:
> mw-list-postfix-userscsi.hu:
> > When you say `monotonic', I think you must mean "monotonic with
> > respect to absolute (not machine) time". But presently, time()
> > reflects the OS's perception of absolute time, and if it is not
> > monotonic, nothing else can be.
>
> I meant monotonic with respect to the hostname, so that no maildir
> filenames can be given the same name (with maildir filenames ending
> in the hostname).

I meant monotonic as a function of time: f(t) increases as t(ime)
increases.

> Considering that mail can arrive at a rate of multiple messages a
> second, and that a hostname can be in use for multiple years, this
> means the measurement needs to be accurate to 1 in 10**10 or better.
>
> There also is the problem of recovering state from backups after
> a disaster causes the machine to be destroyed.
>
> For a brief while I thought that monotonic non-time sequences would
> solve problems, but it looks like they are too fragile.
>

Here is a simple idea that should be inexpensive to implement (maybe
existing hardware can be used).

Every computer needs to have a device with the following components

--- a ticker that is guaranteed to tick at least once every nanosecond
    (a cheap quartz oscillator should do this). The stability of the
    ticking (that is the constancy of the time between consecutive
    ticks) is unimportant; only the frequency of the ticks matters.

--- a counter that is capable of counting the ticks of the ticker.

--- a unique 30 (decimal) digit prime number p.

In other words the device is a clock plus a prime number.

The device is readonly, everything in it is hardcoded, nothing can be
adjusted. It is assumed that the kernel can communicate with the
counter.

The counter, at every tick, returns the next multiple of the prime p,
so it produces the sequence

p, 2*p, 3*p, ...

The count starts at the time of manufacturing, and it does not stop
until the device breaks or runs out of power.

When a program, say an MDA, wants to generate a globally unique name,
just get the counter's current value.

The resulting name (number) is unique on the given computer, because
(at least in theory), the kernel is not capable to ask for the
counter's value twice in one ns.

Assuming the ticker cannot tick more than 1000 times per nanosecond
(or the counter simply does not consider more than 1000 ticks/ns), the
resulting number is globally unique for the next million years. Why?

First, it is clear that on our computer, the generated sequence of
numbers is strictly increasing, that is, the names are locally (with
respect to the device) unique.
 
After 1 million years, the number of ticks is approximately 10^25
(==10**25 in Fortran-speak), so on our computer any number generated in the
next million years by the device will be of the form

   n*p, with n < 10^26

The numbers generated by another device will be of the form

    m*q, with m < 10^26

where q is a different 30 digit prime. Now, if we had a name
collision, that is

           n*p == m*q,

then p would have to divide m. This is impossible since

     p > 10^30

but

     m < 10^26

So how do you assign the 30 digit prime numbers?

Perhaps by vendor:

IBM gets the first one trillion (== 10^12 in the US).
AMD gets the next trillion
etc

Note that there are about 10^28 thirty digit primes, so the above
assignment allows over a quadrillion vendors...

There is no incentive in reusing a vendor's official primes in your
product: the purpose of these devices is not to produce unpredictable
names, but to produce names that are globally unique in this scheme.

Mate

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]