Subject: Re: msg-id

From: John Stanley <[email-masked]>
Date: Fri, 10 Dec 2004 12:10:53 -0800 (PST)

Seth Breidbart <sethb@xxxxxxxxx>:
>> What is important is that the ERROR is known and can be avoided completely
>> by fixing it now.

>No, it can't be avoided completely.

Yes, by using an algorithm that does not have the possibility of 
duplicates. "epochtime.sequence.pid.yy.mm.dd.hh.mm.ss@domain" will not 
repeat.

>> Hmmm. Let's see. I use "sequence number dot epoch time dot process id dot
>> month dot day dot year @ domain". Since THIS epoch time will never
>> reoccur, it cannot be the same as what any other owner of my domain would
>> use. Guaranteed unique.

> Except that another owner of the domain 

There is no other owner at that epochtime. 

>(or another piece of client
>software in use in that domain) used (or will use) "sequence number
>dot process id dot epoch time dot day dot month dot year @ domain",

No, I've already told you the algorithm being used in that domain. And 
since only one process has the process id, two different processes on the 
same system cannot generate the same message id.

>...and gets his pids randomly from 32-bit space (to avoid potential
>attacks based on known-pids).  Oops.

I'm interested in hearing which operating system allows two different 
processes to have the same process id at the same time.

>Genetic testing shows that the results were not the same.

"Your wife had a baby" does not depend on genetic testing. The content of 
the message does not have any effect on the message id.

>> No, you said they caused the SAME violation of the same MUST. Even
>> were that true, the two causes are very different.

>So what?

So you cannot even correctly represent what you said.

>> No, actually it doesn't. It someone tosses one coin per thousand years and 
>> you say it has a once per thousand year chance of coming up heads, you've
>> just said it is a certainty to come up heads.

>No, he didn't.  If a coin is expected to come up heads once per
>thousand years, then either it's extremely biased, or it's expected to
>be tossed twice in a thousand years.

Well, it might be extremely biased, but it certainly doesn't need to be 
tossed twice for the odds to be stated the way they were. If we say the 
odds of you graduating college are unity, does that mean you have to try 
graduating twice?

>You keep claiming that other people don't understand what "expected"
>means, with no evidence other than your own statements.

And theirs.

>> Ah, yes, this old "we cannot specify MUST because a computer somewhere 
>> might crash and violate it anyway."

>Another red herring.  Who said we shouldn't or can't specify "MUST"?

The question was about a MUST be unique clause, which doesn't actually
need to be unique. So, I guess the correct statement should have been:

"We cannot specify a MUST that we really mean because  ...".

>We can't _implement_ it perfectly, because we can't implement
>_anything_ perfectly. 

A nice variant on what I just said. We shouldn't worry about implementing 
what we CAN correctly because there are other things that can make it 
break anyway.

Frank Ellermann <nobody@xxxxxxxxxxxxxxxxx>:

>That might be true, or let's say I don't care.  But we have a
>practical problem with some very old UAs like my "Mozilla 3":

>This monster creates Message-IDs based on the RHS of the From:
>address.  Now we tolerate something like spamhater@invalid as
>an "address".  

This monster was in violation of the standards long before we started
"tolerating" .invalid addresses. If mozilla creates message ids for a
domain that may never see the message at all, then it cannot guarantee it
will be unique.

---

From: Seth Breidbart <[email-masked]>
Date: Fri, 10 Dec 2004 16:23:06 -0500 (EST)

> duplicates. "epochtime.sequence.pid.yy.mm.dd.hh.mm.ss@domain" will not 

You are making the assumption that a new domain owner will continue to
use the same algorithm.  That is not a valid assumption.  A new domain
owner might use a _different_ algorithm.

> There is no other owner at that epochtime. 

So what?  I didn't say there was.

> No, I've already told you the algorithm being used in that domain.

That's the algorithm being used by the current owner now.  A new owner
later might use a different algorithm.

> processes to have the same process id at the same time.

You might read my example more carefully.  Because the new owner used
a _different_ algorithm, different fields matched (e.g. his PID
matched your epoch-time).  Sure, the odds are low; but you don't find
that acceptable.

> the message does not have any effect on the message id.

If you choose to leave out critical data, then any events are "the
same".  The issue here is "are the Message Ids unique?"

> odds of you graduating college are unity, does that mean you have to try 

No, if the odds are unity, then I have to try one time that has a 100%
chance of success.  If the expected number of times is unity, and each
attempt has a probability of 50%, then the expected number of attempts
is 2.

>>means, with no evidence other than your own statements.

And your misunderstanding of their statements or of probability
theory.

> need to be unique.

It does need to be unique.  The protocol fails when it isn't unique.

Note that "need" is always relative to a goal.

> So, I guess the correct statement should have been:
>

That's your statement, not mine.  I say we can specify the MUST.

> what we CAN correctly because there are other things that can make it 

Is that what you're saying?  It certainly isn't what I'm saying.

I'm saying that I'm not worried about sufficiently-low failure
probabilities.  You say that you won't accept them, except that your
examples of what is acceptable to you still have non-zero failure
probabilities.

> If mozilla creates message ids for a domain that may never see the
> message at all, then it cannot guarantee it will be unique.

I own a domain that does not run a news server.  That domain will
never see a usenet message.  Yet use of it in the RHS of a Message-Id
by me can certainly guarantee uniqueness (modulo other people doing
stuff they're not entitled to, which can break any algorithm).

Seth

---

From: Richard Clayton <[email-masked]>
Date: Sun, 12 Dec 2004 01:01:50 +0000

In message <[email-masked]>, Seth Breidbart
<[email-masked]> writes

>owner might use a _different_ algorithm.

there also appears to be an assumption that "domain" is the same as
"host" :-(  For example, if the co-owner of my domain posts at the same
moment as I do (from his machine 100 miles to the south of here) there
may be a clash. However, there's an obvious set of possible fixes to
John's design to tackle that, so it's not a killer observation.

Now in practice we all use software that avoids this problem by other
methods...  (in the case of co-owner and I, there's a unique product ID
included in the algorithm.  I do wonder if @aol.com people can be so
sanguine about this ?)

However since the standard isn't going to specify the exact mechanism as
to how duplicates are avoided, why not just have it concentrate on why
duplicates are a bad thing (stressing that this now means over
substantial time periods) and impress upon implementors that they should
address this issue properly and not make a mess of it by skimping on
message ID length (which I think worries some people)

viz: say what the result should be, stress that it's not a trivial thing
to achieve, and leave exploring the rest of the rathole alone

>I'm saying that I'm not worried about sufficiently-low failure

perhaps the text should specifically address the effect of the failures
(viz: that your new message may fail to propagate, or fail to be
archived)... 

>stuff they're not entitled to, which can break any algorithm).

... so what the text should be saying is that using a RHS which you
don't control is especially undesirable because it means that you may
adversely affect complete strangers.

If we didn't believe that the whole aim is to ensure we only screw up
ourselves, not strangers, then for efficiency of implentations we'd
avoid x@y style IDs altogether and start recommending IDs of the form
opaque@usenet where the opaque value was created by running SHA-1 over
an identifier to which consisted of - let's say - a sequence number
appended to our birth date and GPS co-ordinates of our current location.

However, this opaqueness feels like something that might go wrong from
time to time (in reality, many eons, but the feel would be otherwise)
and we'd never even meet the person who caused it to go wrong for us ...
whereas if we're using our domains, even with a really poor mechanism,
then at least we can go upstairs to the kid's bedroom (or head down
south for the afternoon) and berate the obstructer personally :)

- -- 
richard                                              Richard Clayton

They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.         Benjamin Franklin