We study the convergence of influence networks, where each node changes its state according to the majority of its neighbors. Our main result is a new bound on the convergence time in the synchronous model, solving the classic “Democrats and Republicans” problem. Furthermore, we give a bound for the sequential model in which the sequence of steps is given by an adversary and a bound for the sequential model in which the sequence of steps is given by a benevolent process.
Guest: Barbara Keller
Host: Shantanu Das