[Back]


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, Agadir, Marokko; 2015-05-13 - 2015-05-15; in: "NETYS2015", Springer LNCS, 9466 (2015), ISBN: 978-3-319-26849-1.



English abstract:
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)
http://dx.doi.org/10.1007/978-3-319-26850-7