Gracefullly Degrading Agreement in Directed Dynamic Networks

This project is devoted to the development of the theoretical foundations, models, algorithms and analysis techniques for relaxed distributed agreement in directed dynamic networks. Such networks are characterized by (i) sets of participants (processes) that are a priori unknown and potentially time-varying, (ii) rapidly changing uni-directional connectivity between processes, and (iii) the absence of central control. Instantiated, e.g., by (wireless) sensor networks and ad-hoc networks, such dynamic networks are becoming ubiquitous in many applications nowadays. A natural approach to build robust services despite the dynamic nature of such networks would be to use distributed consensus to agree system-wide on (fundamental) parameters like schedules, operating frequencies, operating modes etc. Unfortunately, however, in larger-scale dynamic networks, this is usually impossible, since solving consensus requires a well-connected and temporarily stable network topology. In order to overcome this fundamental limitation, we propose to consider gracefully degrading variants of consensus, in particular, approximate agreement, where decision values may slightly deviate from each other, and k-set agreement, which may deliver up to k different decisions in case of bad network conditions that e.g. lead to k isolated network partitions. In our project, we will develop network assumptions that both allow to solve, say, k-set agreement, and have some reasonable assumption coverage in real systems. Therefore, our focus will be on weakest (necessary and sufficient) conditions and the analysis of the resulting assumption coverage. Other central part of our project is the development of solution algorithms and their correctness proofs. Particular emphasis will be put on performance of our algorithms, since there is a tradeoff between weak network conditions and the communication and memory complexity of solutions algorithms. Overall, the project shall yield new insights into the fundamental limitations of dynamic networks as well as the development of novel algorithms that solve distributed agreement problems reliably even under very weak communication guarantees.

ADynNet (Gracefully Degrading Agreement in Directed Dynamic Networks) has been devoted to the development of the theoretical foundations, models, algorithms and analysis techniques for distributed agreement in directed dynamic networks. Such networks are characterized by sets of participants that are a priori unknown and potentially time-varying, a rapidly changing uni-directional connectivity between participants, and the absence of any central control. Instantiated, e.g., by wireless sensor networks and ad-hoc networks, such dynamic networks are ubiquitous in many applications nowadays. A natural approach to build robust services in such networks would be to use distributed consensus to agree system-wide on fundamental parameters like schedules, operating frequencies, operating modes etc. In larger-scale dynamic networks, however, this has been considered infeasible, as solving consensus was believed to require a well-connected and temporarily stable network topology. In ADynNet, we showed that this is not necessarily the case: We thoroughly studied consensus solvability in directed dynamic networks controlled by message adversaries, and developed solution algorithms for surprisingly strong message adversaries. Some highlights of our accomplishments are: (i) We developed a precise characterization of the solvability/impossibility border for consensus in such dynamic networks. Surprisingly, point-set topology turned out to be the method of choice for this purpose. (ii) We developed consensus algorithms for several stabilizing message adversaries, including optimal ones that require very short durations of stability. Moreover, we also provided relaxed agreement algorithms such as gracefully degrading k-set agreement and approximate agreement for message adversaries that do not allow consensus. Apart from its primary research results, the work in ADynNet also revealed the utility of knowledge-based analysis and epistemic logic for studying the problems at hand, which stimulated a transdisciplinary follow-up FWF project ByzDEL (Reasoning about Knowledge in Byzantine Distributed Systems, P33600).