Optimal Resilience Asynchronous Approximate Agreement

• Lemma 2. If no non-faulty process halts before or during round \(h\) and all of

them reach round \(h\), then all non-faulty processes eventually advance to round \(h+1\).

• Lemma 3. All non-faulty processes eventually decide and halt.
• Lemma 4 (Validity). For all \(p \in G\) and round \(h\), \(\min{U} \le val^h_p \le \max{U}\).
• Lemma 5. Every pair of non-faulty processes \(p\), \(q\) that complete round \(h\), maintain that \(|values^{h}_{p} \cap values^{h}_{q}| \ge n−t\).
• Lemma 6. The range of non-faulty processes is cut by at least a half \(\delta(U_{i}) \le \delta(U_{i-1})/2\)
• Lemma 7. Let \(k\) denote the minimal round estimation \(k = \min{enough_{r} | r ∈ G}\). Then if all \(p \in G\) complete round \(k\) then \((\forall p,q \in G) | val^{k}_p - val^k_{q} | \le \epsilon\).
• Lemma 8. The number of rounds that any non-faulty process completes is at most \(log_{2}\dfrac{\delta(U)}{\epsilon}\).
• Theorem 2. All non-faulty processes terminate after at most \(log_{2}(\delta(U))/\epsilon)\) rounds, with values that are at most \(\in\) of each other, in the range of the initial values.

• Shows optimal approximate agreement for \(n>3t\) and uses witness technique to ensure that two honest nodes \(i\) and \(j\) have at least \(n-t\) nodes in common by adding one more round of echo after RBC.