Agreeing on a common value among a set of agents is a fundamental problem in distributed computing, which occurs in several variants: In contrast to exact consensus, approximate variants are studied in systems where exact agreement is not possible or required, e.g., in human-made distributed control systems and in the analysis of natural distributed systems, such as bird flocking and opinion dynamics. We study the time complexity of two classical agreement problems: non-terminating asymptotic consensus and terminating approximate consensus. Asymptotic consensus, requires agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values; approximate consensus requires agents to eventually stop setting their outputs, which must then lie within a predefined distance of each other. We prove tight lower bounds on the contraction ratios of asymptotic consensus algorithms subject to oblivious message adversaries, from which we deduce bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented by Charron-Bost et al. (ICALP’16) for certain systems, including the strongest oblivious message adversary in which asymptotic and approximate consensus are solvable. As a corollary we also obtain asymptotically tight bounds for asymptotic consensus in the classical asynchronous model with crashes. Central to the lower-bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.

We study the following data dissemination problem: In a set of n nodes, every node has a unique piece of information. The communication of the nodes is organized in discrete synchronous lock-step rounds. In each round every node sends all currently known pieces of information to all other nodes. Which nodes receive this message is determined by the actual communication graph, which may change from round to round. Recently, Charron-Bost, Függer, and Nowak proved an upper bound of O(nlogn) rounds for the case where every communication graph is an arbitrary rooted tree. We present a new formalism, which facilitates a concise proof of this result. Moreover, we establish linear-time data dissemination bounds for certain subclasses of rooted trees. In particular, we prove that only (n−1) rounds are needed if the underlying graph is a directed path. An analogous result for undirected paths is also established. Furthermore, for trees with a fixed root we relate the dissemination time to the sizes of the subtrees of the root.

We consider the problem of solving consensus using deterministic algorithms in a synchronous dynamic network with unreliable, directional point-to-point links, which are under the control of a message adversary. In contrast to the large body of existing work that focuses on message adversaries that pick the communication graphs from a predefined set of candidate graphs arbitrarily, we consider message adversaries that also allow to express eventual properties, like stable periods that occur only eventually. Such message adversaries can model systems that exhibit erratic boot-up phases or recover after repeatedly occurring, massive transient faults. We precisely determine how much eventual stability is necessary and sufficient, and provide an optimal consensus algorithm. Unlike in the case of longer stability periods, where standard algorithms can be adapted for solving consensus, different algorithmic techniques are needed in the case of short-lived stability.

We study distributed agreement in synchronous directed dynamic networks, where an omniscient message adversary controls the presence/absence of communication links. We prove that consensus is impossible under a message adversary that guarantees weak connectivity only, and introduce eventually vertex-stable source components (VSSCs) as a means for circumventing this impossibility: A VSSC ( k , d ) message adversary guarantees that, eventually, there is an interval of d consecutive rounds where every communication graph contains at most k strongly connected components consisting of the same processes (with possibly varying interconnect topology), which have no incoming links from outside processes. We present a consensus algorithm that works correctly under a VSSC ( 1 , 4 E + 2 ) message adversary, where E is the dynamic network depth. Our algorithm maintains local estimates of the communication graphs, and applies techniques for detecting network stability and univalent system configurations. Several related impossibility results and lower bounds, in particular, that neither a VSSC ( 1 , E − 1 ) message adversary nor a VSSC ( 2 , ∞ ) one allow to solve consensus, reveal that there is not much hope to deal with (much) stronger message adversaries here. However, we show that gracefully degrading consensus, which degrades to general k -set agreement in case of unfavorable network conditions, allows to cope with stronger message adversaries: We provide a k -universal k -set agreement algorithm, where the number of system-wide decision values k is not encoded in the algorithm, but rather determined by the actual power of the message adversary in a run: Our algorithm guarantees at most k decision values under a VSSC ( n , d ) + MAJINF ( k ) message adversary, which combines VSSC ( n , d ) (with some small value of d , ensuring termination) with some information flow guarantee MAJINF ( k ) between certain VSSCs (ensuring k -agreement). Since related impossibility results reveal that a VSSC ( k , d ) message adversary is too strong for solving k -set agreement and that some information flow between VSSCs is mandatory for this purpose as well, our results provide a significant step towards the exact solvability/impossibility border of general k -set agreement in directed dynamic networks. Finally, we relate (the eventually-forever-variants of) our message adversaries to failure detectors. It turns out that even though VSSC ( 1 , ∞ ) allows to solve consensus and to implement the Ω failure detector, it does not allow to implement Σ. This contrasts the fact that, in asynchronous message-passing systems with a majority of process crashes, ( Σ , Ω ) is a weakest failure detector for solving consensus. Similarly, although the message adversary VSSC ( n , d ) + MAJINF ( k ) allows to solve k -set agreement, it does not allow to implement the failure detector Σ k , which is known to be necessary for k -set agreement in asynchronous message-passing systems with a majority of process crashes. Consequently, it is not possible to adapt failure-detector-based algorithms to work in conjunction with our message adversaries.

In this work we study the performance of asymptotic and approximate consensus algorithms in dynamic networks. The asymptotic consensus problem requires a set of agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values. This problem, and the related approximate consensus problem, are fundamental building blocks in distributed systems where exact consensus among agents is not required, e.g., man-made distributed control systems, and have applications in the analysis of natural distributed systems, such as flocking and opinion dynamics. We prove new nontrivial lower bounds on the contraction rates of asymptotic consensus algorithms, from which we deduce lower bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented in [Charron-Bost et al., ICALP'16] for certain classes of networks that include classical failure assumptions, and confine the search for optimal bounds in the general case. Central to our lower bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.

We present a k-set agreement algorithm for synchronous dynamic distributed systems with unidirectional links controlled by an omniscient adversary. Our algorithm automatically adapts to the actual network properties: If the network is sufficiently well-connected, it solves consensus, while degrading gracefully to general k-set agreement in less well-behaved runs. The algorithm is oblivious to the maximum number of system-wide decision values k, which is bounded by the number of certain strongly connected components occurring in the dynamically changing network in a run. Related impossibility results reveal that this bound is close to the solvability border for k-set agreement. To the best of our knowledge, this is the first consensus algorithm that degrades in a graceful way in a dynamic network.