@inproceedings{c0234221779847e6b9f842e3a3550c32,
title = "Brief Announcement: Gracefully Degrading Consensus and k-Set Agreement under Dynamic Link Failures",
abstract = "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.",
keywords = "Distributed algorithms, Dynamic networks, Gracefully degrading consensus, K-set agreement",
author = "Manfred Schwarz and Kyrill Winkler and Ulrich Schmid and Martin Biely and Peter Robinson",
year = "2014",
month = jul,
doi = "10.1145/2611462.2611506",
language = "English",
isbn = "9781450329446",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "341--343",
booktitle = "PODC'14",
address = "United States",
note = "2014 ACM Symposium on Principles of Distributed Computing, PODC'14 ; Conference date: 15-07-2014 Through 18-07-2014",
}