Re: An e-mail web of trust

On 2004-03-03 11:36:28 -0500, Alan DeKok wrote:
> "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.

Right. Also most legitimate messages are probably exchanged between
parties which have communicated before so there is a path of length one
between them.

>   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.

There should probably be some distributed search algorithm, like in P2P
networks. I did read up a bit on searching scale-free graphs (thanks for
the google-fodder!) over the weekend, and while I haven't found The
Solution(TM), there are a few leads which look quite interesting.

> > >   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.

Yup. But I don't think would happen. Certainly not in the web of trust
itself, although there could be a monopolization in the path finding
service.

	hp

--
   _  | Peter J. Holzer    | I think we need two definitions:
|_|_) | Sysadmin WSR       | 1) The problem the *users* want us to solve
| |   | [email protected]         | 2) The problem our solution addresses.
__/   | http://www.hjp.at/ |    -- Phillip Hallam-Baker on spam

[demime 0.99d.1 removed an attachment of type application/pgp-signature]