Some Experimental Results
Voting: not time-efficient (1/m efficiency); ave err is bad for large f, but should be much better for small f
Spot-checking: time-efficient (only about p loss in efficiency); good err rate (even when f is > 50%!), but may be worse with small f or few work blocks
Blacklisting: can quickly eliminate saboteurs
Proposed solution: Combine m=2 voting (for small-f cases), and spot-checking (for large-f cases). Use backtracking and blacklisting for saboteurs.
- 2x to 3x slowdown, but very high reliability, even with saboteurs
- Guaranteed 2x to 3x max. slowdown may be acceptable for volunteer computing