Check out the new USENIX Web site. next up previous
Next: Auditing Up: Algorithm Previous: Basic Read Protocol

Probabilistic Checking

For each read request, there is a certain probability that a client will send the same request to a master and compare the slave and master results. This ``double-check'' probability is a system parameter - it should be small enough so it does not excessively increase the workload on the masters, but large enough so it guarantees that a malicious slave is caught ``red-handed'' quickly.

As described in the previous section, for every read it handles, a slave has to sign a ``pledge'' packet that contains a copy of the request, the content version time-stamped by the master and the secure hash of the result (as computed by the slave). Should the slave act maliciously and return an incorrect answer, the ``pledge'' packet becomes an irrefutable proof of its dishonesty. Once a slave server is proven malicious it can be excluded from the system so it can do no further harm.

It is important to notice that the way the ``pledge'' packets are constructed makes impossible for a client to ``frame'' an innocent slave server - unless that client is able to fake the slave's digital signature. The only harm a client can do is to abuse its ``double-check'' quota (by double-checking all the slave responses instead of a small fraction of them). However, by keeping track on the number of double-check requests it receives from each of its clients, a master can identify statistically anomalous client behavior, which most likely indicates a ``greedy'' client. The master can then enforce fair play by simply ignoring a large fraction of the double-check requests coming from clients suspected to be greedy.


next up previous
Next: Auditing Up: Algorithm Previous: Basic Read Protocol
Popescu Bogdan
2003-06-11