A Characterization of Dynamic Networks Where Consensus Is Solvable

摘要

We consider the Consensus problem in arbitrary dynamic networks. A dynamic network is a communication network whose topology evolves from round to round. We make no assumptions on the possible topologies. We give the first complete necessary and sufficient condition for dynamic networks where it is possible to solve Consensus. We show that we can complement the necessary condition for solvability of Consensus given, in the context of omission faults, in [GPU] in the context of dynamic networks. We prove that this condition is actually sufficient by presenting a new Consensus algorithm. This algorithm is based upon reconstructing a partial, but significant, view of the actual communications that occurred during the execution.