Advogato Trust Metric

The TrustMetric used by AdvoGato. It is an example of a CapacityConstrainedFlowNetwork.

From the user's point of view, it's pretty simple. When you create an account, you have very few privileges. However, you can 'certify' other people, and they can certify you. At present, the certification is simply a three-valued enum: Apprentice, Journeyer, or Master. This induces a nice big graph.

The next step is automatic evaluation of the trust metric. There is a set of users from which all trust flows (currently hardwired to be raph, miguel, federico, and alan). The evaluation itself is essentially a network maximum flow solver, for which nice efficient algorithms exist. The people reached by the flow are those accepted by the trust metric. With the three levels, the maxflow is computed three times: once with just the Master certs, once with Master and Journeyer, and once with all three.

Like all examples of a CapacityConstrainedFlowNetwork, the AdvogatoTrustMetric is robust against noisy or malicious cert data. It effectively blocks large numbers of people from being certified who don't meet the criteria. At the same time, people who do meet the criteria now routinely get certified within an hour of joining, thanks in part to the 'many eyes' nature of the process.

-- RaphLevien

An enhancement of the evaluation algorithm is to mandate a requirement that for each user to be certified at a level, they must have more than one certificate from other people, at that level. Funnily enough, this can be performed with _another_ maximum flow computation - one per user per level.

This makes the system much more robust: in the current AdvogatoTrustMetric system, only a single certification by one trusted Master is sufficient to create another trusted Master...

-- Luke Leighton