[Zurück]

M. Schwarz, K. Winkler, U. Schmid, M. Biely, P. Robinson:
"Brief Announcement: Gracefully Degrading Consensus and k-Set Agreement under Dynamic Link Failures";
Vortrag: 33th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC), Paris, France; 15.07.2014 - 18.07.2014; in: "Proceedings of the 33th ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing", ACM, (2014), S. 341 - 343.

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.

Distributed algorithms; dynamic networks; k-set agreement; gracefully degrading consensus

http://dx.doi.org/10.1145/2611462.2611506