A web of trust would not need to be too deep to start working. After all, it takes just a couple of acquaintance hops to connect 90% of the people on Earth. Not sure about the 6-degrees-of-separation thing, but it's probably on the order of that.<p>The greater problem of a distributed system would be public key revocation, because you have to go through your entire contacts list to publish a new key.