Talks and Poster Presentations (with Proceedings-Entry):
M. Biely, P. Robinson, U. Schmid, M. Schwarz, K. Winkler:
"Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks";
Talk: The international Conference on NETworked sYStems,
- 2015-05-15; in: "NETYS2015",
We present the first consensus/k-set agreement algorithm
for synchronous dynamic networks with unidirectional links, controlled
by an omniscient message adversary, which automatically adapts to the
actual network properties in a run: If the network is sufficiently well-
connected, it solves consensus, while it degrades gracefully to general k-
set agreement in less well-connected communication graphs. The actual
number k of system-wide decision values is determined by the number
of certain vertex-stable root components occurring in a run, which are
strongly connected components without incoming links from outside.
Related impossibility results reveal that our condition is reasonably close
to the solvability border for k-set agreement.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.