Talks and Poster Presentations (with Proceedings-Entry):
M. Schwarz, K. Winkler, U. Schmid, M. Biely, P. Robinson:
"Brief Announcement: Gracefully Degrading Consensus and k-Set Agreement under Dynamic Link Failures";
Talk: 33th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC),
Paris, France;
2014-07-15
- 2014-07-18; in: "Proceedings of the 33th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing",
ACM,
(2014),
341
- 343.
English 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 suffi ciently 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; k-set agreement; gracefully degrading consensus
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2611462.2611506
Created from the Publication Database of the Vienna University of Technology.