Asynchronous Message-Passing Binary Consensus over Non-Complete Graphs

Goitom Weldehawaryat, Stephen D. Wolthusen

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

Cite this