Deterministic Accuracy Sample Clauses

Deterministic Accuracy. For deterministic accuracy, we make guarantees based on the accuracy ratio α (ratio of the weight of accurate processes to the weight of non-faulty processes) and the fault ratio of the system r (ratio of the weight of faulty processes to the weight of non-faulty processes). We show that if α > 3/4 for each iteration and if the initial fault ratio r0 < 1/2, then the algorithm guarantees accuracy. Then we relax this requirement and show that it is sufficient that α > (1/2 + d) for each iteration such that r0 < 2d, to guarantee accuracy. We first show that as long as α > 1/2 for each iteration, r never increases if we update weights only on error. This enables us to make guarantees just based on the initial fault ratio of the system. The proof crucially depends on the fact that we update the weights of inaccurate processes only when the algorithm chooses the incorrect value.