Oberseminar
Hamed Hosseinpour, University of Hamburg
November 27, 2020, 12:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: Analysis of several known protocols for solving Consensus Problems
Consensus problem is defined as follow: We are given a graph $G(V,E)$. Each agent (node) has initially an opinion out of [k] possible opinions such that $k\leq n$. The goal is to design a simple randomised protocol which is fast enough and changes the opinions of (some) agents in each step. We are certain to show that utilising this protocol leads the system to reach a state in which all agents share the same opinion. As the most interesting protocols we are about to compare VOTER, 2-choices, 3-majority and Undecided dynamics protocols. Moreover, we show undecided dynamic protocol will solve consensus problem way faster than others i.e., it runs in poly-log time in |V|. This, also, answer an open question proposed by Becchetti et al. [Distributed computing 2017].