Stabilization Time in Minority Processes

Abstract

We analyze the stabilization time of minority processes in graphs. A minority process is a dynamically changing coloring, where each node repeatedly changes its color to the color which is least frequent in its neighborhood. First, we present a simple $\Omega (n^2)$ stabilization time lower bound in the sequential adversarial model. Our main contribution is a graph construction which proves a $\Omega (n^{2-\epsilon })$ stabilization time lower bound for any $\epsilon >0$. This lower bound holds even if the order of nodes is chosen benevolently, not only in the sequential model, but also in any reasonable concurrent model of the process.