Re: the O(N^2) problem

[Owen DeLong <owen () delong com>]

On Apr 13, 2008, at 5:36 PM, Edward B. DREGER wrote:

> Bottom line first:
>
> We need OOB metadata ("trust/distrust") information exchange that  
> scales
> better than the current O(N^2) nonsense, yet is not PKI.
Not sure why PKI should be excluded, but, so far, this is too abstract
to know what the question is...

> And now, the details... which ended up longer reading than I intended.
> My apologies.  As Mark Twain said, "I didn't have time to write a  
> short
> letter, so I wrote a long one instead." :-)
>
> When it comes to establishing trust:
>
> * The current SMTP model is O(N^2);
I don't see SMTP as even a "trust" model since there's pretty much
nothing trustworthy in SMTP.

> * I posit that the current IP networking model is sub-O(N);
Again, I'm not seeing IP as a trust model, but, YMMV.

> * PKI models are pretty much O(1).
>
> Polynomial-order just doesn't scale well.  It's mathematical fact, and
> particularly painful when the independent variable is still increasing
> quickly.
Sure.

> Many operators seem to reject PKI as "power in too few hands".  I'll  
> not
> disagree with that.
Depends on the PKI.  For example, the PGP/GPG Web of Trust concept
pretty much lets each individual build their own trust model to whatever
O(x) they choose where greater values of x require more effort and also
provide greater security/trust granularity and lower values of x involve
greater trust of others that you claim you can trust and less direct  
effort
on your part.
> Let's also draw upon operational lessons from a couple old-timers.  I
> recall using a critter known as "NNTP".  And once upon a time,  
> before my
> days on the Internet, lived a funny little beast called "UUCP".
I remember UUCP.  It was pretty much O(n^2).

> We track email quality from all mailservers that hit us.  I can whip  
> up
> a list of MXes/organizations that I'm willing to "trust" -- and let's
> leave that term imprecisely-defined for now.
Uh, OK.  Starting to understand what the question might be aiming
towards.

> Here's what I propose:
>
> Establish a "distrust protocol".  Let path weight be "distrust".  The
> "trust path" is of secondary importance to "path weight", although not
> completely irrelevant.  SMTP endpoint not in graph?  Fine; have some
> default behavior.
>
> Let _trust_ be semi-transitive, a la BGP -- a technology that we know,
> understand, and at least sort of trust to run this crazy, giant  
> network
> that dwarfs even a 50M-user provider.
>
> Let actual _content_ still be end-to-end, so that we do not simply
> reincarnate NNTP or UUCP.
Now I'm lost again.  You've mixed so many different metaphors from
interdomain routing to distance-vector computaton to store-and-forward
that I simply don't understand what you are proposing or how one
could begin to approach implementing it or what problem you seem
to think it solves (although it sort of seems like you're wanting to  
attack
the trustworthiness of email to battle SPAM through some mechanism
that depends only on the level of trust for the (source, arrival path)
tuple from whence it came.

What am I missing?

Owen