Consensus Problems in Population Protocol Model

Abstract

This thesis considers plurality consensus problems in the population protocol model. We design and analyze protocols to solve these consensus problems time and space efficiently. In the population protocol model, we consider n agents that interact in randomly chosen pairs, one pair per time step. In the plurality consensus problem, each of the n agents initially has one of the k opinions. The goal is for all agents to agree on the initial most frequent opinion among the population.