Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs

Goitom Weldehawaryat; Stephen D. Wolthusen

doi:10.1109/NSW.2013.6609188

Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs

Goitom Weldehawaryat, Stephen D. Wolthusen

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

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 Erdfüs-Ré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.

Original language	English
Title of host publication	Proceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013)
Publisher	IEEE Computer Society Press
Pages	9-15
DOIs	https://doi.org/10.1109/NSW.2013.6609188
Publication status	Published - 2013

Access to Document

10.1109/NSW.2013.6609188

Cite this

@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{\"u}s-R{\'e}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",

}

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 Erdfüs-Ré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 Erdfüs-Ré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 -