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

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

10 Citations (Scopus)

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
Title of host publication	Networked Systems
Subtitle of host publication	3rd International Conference, NETYS 2015, Revised Selected Papers
Editors	Ahmed Bouajjani, Hugues Fauconnier
Publisher	Springer
Pages	109-124
ISBN (Electronic)	978-3-319-26850-7
ISBN (Print)	978-3-319-26849-1
DOIs	https://doi.org/10.1007/978-3-319-26850-7_8
Publication status	Published - May 2015
Externally published	Yes
Event	3rd International Conference on Networked Systems, NETYS 2015 - Agadir, Morocco Duration: 13 May 2015 → 15 May 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications)
Publisher	Springer
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	13/05/15 → 15/05/15

Access Output

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

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

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 Computer Communication Networks and Telecommunications); Vol. 9466). Springer . https://doi.org/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 , 2015. pp. 109-124 (Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications)).

@inproceedings{e45565fd73254ad485a54d589d4cb1ae,

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",

year = "2015",

month = may,

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

language = "English",

isbn = "978-3-319-26849-1",

series = "Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications)",

publisher = "Springer ",

pages = "109--124",

editor = "Ahmed Bouajjani and Hugues Fauconnier",

booktitle = "Networked Systems",

note = "3rd International Conference on Networked Systems, NETYS 2015 ; Conference date: 13-05-2015 Through 15-05-2015",

}

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 Computer Communication Networks and Telecommunications), vol. 9466, Springer , pp. 109-124, 3rd International Conference on Networked Systems, NETYS 2015, Agadir, Morocco, 13/05/15. 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 , 2015. p. 109-124 (Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications); Vol. 9466).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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/5

Y1 - 2015/5

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 - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84961180981&origin=recordpage

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

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

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-319-26849-1

T3 - Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications)

SP - 109

EP - 124

BT - Networked Systems

A2 - Bouajjani, Ahmed

A2 - Fauconnier, Hugues

PB - Springer

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

Y2 - 13 May 2015 through 15 May 2015

ER -

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 . 2015. p. 109-124. (Lecture Notes in Computer Science (including subseries Computer Communication Networks and Telecommunications)). doi: 10.1007/978-3-319-26850-7_8

Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this