The University of Arizona

Please note that this event has ended!

The Distributed Binary Consensus Problem and the Voter Model

Graduate Student Colloquium

The Distributed Binary Consensus Problem and the Voter Model
Series: Graduate Student Colloquium
Location: Math 501
Presenter: Conner Hatton, University of Arizona

Given a network of nodes in which each state has a binary state, e.g., 0 or 1, the distributed binary consensus problem is to create a distributed protocol in which the states will reach consensus on the state that was held by the initial majority of nodes. In this talk, I will introduce the voter model on the complete graph as a nondeterministic protocol for the distributed binary consensus problem. The aim of this talk is to highlight a weak law of large numbers results for the voter model via the fluid limit which, in this case, is a set of ordinary differential equations that give the "average" trajectory of the process. I will then discuss the implications of the fluid limit and how it limits the utility of the voter model as a protocol for the distributed binary consensus problem. We will then use the same techniques to analyze the ternary voter model proposed by Perron, Vasudevan, and Vojnovic in a 2008 paper where they found that adding an additional 'undecided' state to the voter model results in an efficient and robust protocol for the distributed binary consensus problem.