Re: An e-mail web of trust

"Peter J. Holzer" <[email protected]> wrote:
> There is still the problem of determining the path efficiently.
> You have a few tens of millions nodes (if you are using domain names -
> more if you are using individual mail addresses), each with dozens to
> hundreds edges, and determining some path (prefererrably a rather short
> path) in that graph should be possible in a few seconds to minutes to be
> acceptable to users.

  Which is why you'd cache it for many situations.  The distribution
of sent email is not even across destination domains.  Probably 90% of
the messages go to 10% of the domains.  So with caching, the work the
sender does is minimal.  Caching also helps the recipient, because
they don't have to check the paths for most of the messages.

  The larger problem is how to query AT&T (for example) to find
*which* connections you want.  If you have all of the connection
information locally, you can run a local walking algorithm, which will
be fairly fast.  If you have to check for the existence of each edge
via DNS, it becomes a lot more difficult.

  The answer is probably for the recipients to publish multiple paths
to well-known, and well-connected systems.  Since the originator is
also a recipient, he has to publish similar paths, and splicing the
two becomes fairly trivial.

> >   The only problem is that the web of trust now becomes more fragile.
> 
> Does it? I think by distributing the information it can be made more
> robust on the whole.

  So long as there are redundancies.  If everyone chooses to only go
through AT&T, and it goes down, they're stuck.

> Can provide a reference for the method? I'd like to look at it (I'm
> afraid my knowledge of graph-theory is several years out of date, and
> was never very thorough to begin with).

  My knowledge of this is limited to reading a number of "pop" science
articles on it.  Searching google for "scale-free graphs" returns a
number of links which may be useful.

  This one is nice:

http://www.cs.bgu.ac.il/~barakw/colloquium/havlin/

  strictly for the comment that the diameter (e.g. distance between
nodes) is log(log(N)).  That looks like it will scale pretty well.

  A review of a book covering the topic is:

http://www.americanscientist.org/template/BookReviewTypeDetail/assetid/17189;jsessionid=baa7Ojk6WrThAO

  An old article about scale-free graphs & the net is:

http://www.economist.com/science/displayStory.cfm?story_id=1365118

  This has a nice comment about the difficulty of stopping viruses in
a normal "random" network: It's hard.  But in a scale-free network,
stopping viruses at a few key nodes means that their propogation can
be signficantly reduced.

  I'm optimistic that similar arguments apply to the adoption of new
anti-spam systems.  Once a few key players deploy it, and everyone
sees it's useful, the deployment to the rest of the net may be very
quick.

  Alan DeKok.