[Back]


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.