Approximate Agreement Asynchronous Systems

An algorithm described by Dolev et al. [7] works by successive approximation. That is, each cycle approaches the target with a guaranteed rate of convergence. The most interesting part of this algorithm is that it works in both synchronous and asynchronous systems (with ). The conditions are similar to those of the consensus problem: all correct processes end up stopping with output values in each other, and all the values decided are within the range of input values of all the correct processes. For synchronous systems, the convergence rate depends on the ratio of the number of failed processes to the total number of processes. Convergence is guaranteed if n > 3t. For asynchronous systems, convergence is ensured when n > 5t. The asynchronous algorithm is the same as above, except that each process only listens for n-t messages, does not select a default value, and executes the function in the list. Interestingly, although exact consensus is impossible in a completely asynchronous system, one can choose arbitrarily small to get as close as possible to consensus. The issue of approximate agreement is not necessarily a problem of consensus, but is related and worth mentioning. We can modify the problem of the Byzantine generals so that each process enters into a real value, not a binary value, and all processes must eventually opt for real values that are in each other. Note that it is then equivalent to the problem of consensus with real values.

The synchronous algorithm essentially works as follows. Each process sends its value to all other processes. If a failed process does not send a value, a default value, e.B. 0, is selected. Each process then executes the function for the n real values. Roughly speaking, the function f is chosen in such a way that the lowest and highest t-values are eliminated from the list and the average of the rest is taken; defective processes cannot therefore influence the convergence of values. To show that it is necessary to have n > 3t, suppose n = 3t. If all faulty processes send a very high value to correct the process p and a very low value to correct the process q, then p and q take their averages to two sets of completely different numbers and do not converge. However, if n = 3t + 1, then p and q have a value that overlaps at their median and converge (very slowly) towards each other. .