We investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both syn- chronous and partially synchronous networks, approximate consensus is solvable if and only if permanently, the communication graph has a rooted spanning tree. The striking point is that the spanning tree may continually change over time without preventing nodes from converging to consensus. Actually the class of averaging algorithms, which have the benefit of being memoryless and requiring no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm.
We develop a proof strategy which consists in a reduction to the nonsplit networks. It dramatically improves the best known upper bound on the decision times of averaging algo- rithms and yields a non-averaging algorithm for approximate consensus in non-anonymous networks with a decision time that is quadratic in the number of nodes. We also prove that a general upper bound on the decision times of averaging algorithms has to be exponential, shedding light on the high price of anonymity.
Finally we apply our results to networked systems with a fixed topology and benign fault models to show that with n processes, up to 2n − 3 of link faults per round can be tolerated for approximate consensus, increasing by a factor 2 the tight bound for exact consensus established by Santoro and Widmayer.