Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. / Weldehawaryat, Goitom; Wolthusen, Stephen D.

Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013). IEEE Computer Society Press, 2013. p. 9-15.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Standard

Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. / Weldehawaryat, Goitom; Wolthusen, Stephen D.

Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013). IEEE Computer Society Press, 2013. p. 9-15.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Weldehawaryat, G & Wolthusen, SD 2013, Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. in Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013). IEEE Computer Society Press, pp. 9-15. https://doi.org/10.1109/NSW.2013.6609188

APA

Weldehawaryat, G., & Wolthusen, S. D. (2013). Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. In Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013) (pp. 9-15). IEEE Computer Society Press. https://doi.org/10.1109/NSW.2013.6609188

Vancouver

Weldehawaryat G, Wolthusen SD. Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. In Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013). IEEE Computer Society Press. 2013. p. 9-15 https://doi.org/10.1109/NSW.2013.6609188

Author

Weldehawaryat, Goitom ; Wolthusen, Stephen D. / Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs. Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013). IEEE Computer Society Press, 2013. pp. 9-15

BibTeX

@inproceedings{902b2c5b9d0b49b4ac036a1a61800df4,
title = "Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs",
abstract = "While the fundamental problem of consensus in distrbuted systems has been studied extensively, this has mostly focused on shared-memory and to a lesser extent on asynchronous message-passing models. However, a natural extension is to consider the case of a asynchronous message-passing model over non-complete graphs. In this paper, we study the problem of binary consensus problem over non-complete graphs using Erdfüs-Rényi and describe an algorithm which not only yields the desired primary result, but also achieves this with the stronger constraint of messages from a given source reaching their respective sinks over k edge-disjoint spanning trees by extending Correia et al.'s variant of Ben-Or's algorithm.",
author = "Goitom Weldehawaryat and Wolthusen, {Stephen D.}",
year = "2013",
doi = "10.1109/NSW.2013.6609188",
language = "English",
pages = "9--15",
booktitle = "Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013)",
publisher = "IEEE Computer Society Press",

}

RIS

TY - GEN

T1 - Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs

AU - Weldehawaryat, Goitom

AU - Wolthusen, Stephen D.

PY - 2013

Y1 - 2013

N2 - While the fundamental problem of consensus in distrbuted systems has been studied extensively, this has mostly focused on shared-memory and to a lesser extent on asynchronous message-passing models. However, a natural extension is to consider the case of a asynchronous message-passing model over non-complete graphs. In this paper, we study the problem of binary consensus problem over non-complete graphs using Erdfüs-Rényi and describe an algorithm which not only yields the desired primary result, but also achieves this with the stronger constraint of messages from a given source reaching their respective sinks over k edge-disjoint spanning trees by extending Correia et al.'s variant of Ben-Or's algorithm.

AB - While the fundamental problem of consensus in distrbuted systems has been studied extensively, this has mostly focused on shared-memory and to a lesser extent on asynchronous message-passing models. However, a natural extension is to consider the case of a asynchronous message-passing model over non-complete graphs. In this paper, we study the problem of binary consensus problem over non-complete graphs using Erdfüs-Rényi and describe an algorithm which not only yields the desired primary result, but also achieves this with the stronger constraint of messages from a given source reaching their respective sinks over k edge-disjoint spanning trees by extending Correia et al.'s variant of Ben-Or's algorithm.

U2 - 10.1109/NSW.2013.6609188

DO - 10.1109/NSW.2013.6609188

M3 - Conference contribution

SP - 9

EP - 15

BT - Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013)

PB - IEEE Computer Society Press

ER -