The Distributed Binary Consensus Problem and the Voter Model
Graduate Student Colloquium
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.
