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



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.
Original languageEnglish
Title of host publicationProceedings of the 2013 IEEE 2nd International Workshop on Network Science (NSW 2013)
PublisherIEEE Computer Society Press
Publication statusPublished - 2013
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 23259065