Gracefully degrading consensus and k-set agreement in directed dynamic networks

Martin Biely; Peter Robinson; Ulrich Schmid; Manfred Schwarz; Kyrill Winkler

doi:10.1007/978-3-319-26850-7_8

Gracefully degrading consensus and k-set agreement in directed dynamic networks

Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, Kyrill Winkler

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Scopus citations

Abstract

We present (This work has been supported the Austrian Science Fund (FWF) project P26436 (SIC) and S11405 (RiSE).) 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.

Original language	English (US)
Title of host publication	Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers
Editors	Ahmed Bouajjani, Hugues Fauconnier
Publisher	Springer Verlag
Pages	109-124
Number of pages	16
ISBN (Print)	9783319268491
DOIs	https://doi.org/10.1007/978-3-319-26850-7_8
State	Published - 2015
Externally published	Yes
Event	3rd International Conference on Networked Systems, NETYS 2015 - Agadir, Morocco Duration: May 13 2015 → May 15 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9466
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Networked Systems, NETYS 2015
Country/Territory	Morocco
City	Agadir
Period	5/13/15 → 5/15/15

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-26850-7_8

Cite this

Biely, M., Robinson, P., Schmid, U., Schwarz, M., & Winkler, K. (2015). Gracefully degrading consensus and k-set agreement in directed dynamic networks. In A. Bouajjani, & H. Fauconnier (Eds.), Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers (pp. 109-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9466). Springer Verlag. https://doi.org/10.1007/978-3-319-26850-7_8

Gracefully degrading consensus and k-set agreement in directed dynamic networks. / Biely, Martin; Robinson, Peter; Schmid, Ulrich et al.
Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers. ed. / Ahmed Bouajjani; Hugues Fauconnier. Springer Verlag, 2015. p. 109-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9466).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Biely, M, Robinson, P, Schmid, U, Schwarz, M & Winkler, K 2015, Gracefully degrading consensus and k-set agreement in directed dynamic networks. in A Bouajjani & H Fauconnier (eds), Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9466, Springer Verlag, pp. 109-124, 3rd International Conference on Networked Systems, NETYS 2015, Agadir, Morocco, 5/13/15. https://doi.org/10.1007/978-3-319-26850-7_8

Biely M, Robinson P, Schmid U, Schwarz M, Winkler K. Gracefully degrading consensus and k-set agreement in directed dynamic networks. In Bouajjani A, Fauconnier H, editors, Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers. Springer Verlag. 2015. p. 109-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-26850-7_8

Biely, Martin ; Robinson, Peter ; Schmid, Ulrich et al. / Gracefully degrading consensus and k-set agreement in directed dynamic networks. Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers. editor / Ahmed Bouajjani ; Hugues Fauconnier. Springer Verlag, 2015. pp. 109-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9ab2f626282448aaa8ce8c22eab90930,

title = "Gracefully degrading consensus and k-set agreement in directed dynamic networks",

abstract = "We present (This work has been supported the Austrian Science Fund (FWF) project P26436 (SIC) and S11405 (RiSE).) 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.",

author = "Martin Biely and Peter Robinson and Ulrich Schmid and Manfred Schwarz and Kyrill Winkler",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 3rd International Conference on Networked Systems, NETYS 2015 ; Conference date: 13-05-2015 Through 15-05-2015",

year = "2015",

doi = "10.1007/978-3-319-26850-7_8",

language = "English (US)",

isbn = "9783319268491",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "109--124",

editor = "Ahmed Bouajjani and Hugues Fauconnier",

booktitle = "Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers",

}

TY - GEN

T1 - Gracefully degrading consensus and k-set agreement in directed dynamic networks

AU - Biely, Martin

AU - Robinson, Peter

AU - Schmid, Ulrich

AU - Schwarz, Manfred

AU - Winkler, Kyrill

PY - 2015

Y1 - 2015

N2 - We present (This work has been supported the Austrian Science Fund (FWF) project P26436 (SIC) and S11405 (RiSE).) 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.

AB - We present (This work has been supported the Austrian Science Fund (FWF) project P26436 (SIC) and S11405 (RiSE).) 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.

UR - http://www.scopus.com/inward/record.url?scp=84961180981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961180981&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-26850-7_8

DO - 10.1007/978-3-319-26850-7_8

M3 - Conference contribution

AN - SCOPUS:84961180981

SN - 9783319268491

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 124

BT - Networked Systems - 3rd International Conference, NETYS 2015, Revised Selected Papers

A2 - Bouajjani, Ahmed

A2 - Fauconnier, Hugues

PB - Springer Verlag

T2 - 3rd International Conference on Networked Systems, NETYS 2015

Y2 - 13 May 2015 through 15 May 2015

ER -

Gracefully degrading consensus and k-set agreement in directed dynamic networks

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this