Common Contracts

Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks

September 10th, 2018

• Filed
  September 10th, 2018

Abstract. 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 in- troduce vertex-stable root components (VSRCs) as a means for circumventing this impossibility: A VSRC(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 con- sisting of the same processes (with possibly varying interconnect topology), which have at most out-going links to the remaining processes. We present a consensus algorithm that works correctly under a VSRC(1, 4H + 2) message adversary, where H is the dynamic causal network diameter. Our algorithm maintains local estimates of the communication graphs, and applies techniques for detecting network stability and univalent syst