You could randomize the tests + test everyone at the same time. So every r(n) cycles send a micro problem with a known precomputed locally verified solution. Compare solutions, kick and ban node if wrong.