  Population protocols are a model for distributed computing that is focused on
simplicity and robustness. A system of $n$ identical agents (finite state
machines) performs a global task like electing a unique leader or determining
the majority opinion when each agent has one of two opinions. Agents
communicate in pairwise interactions with randomly assigned communication
partners. Quality is measured in two ways: the number of interactions to
complete the task and the number of states per agent. We present protocols for
the majority problem that allow for a trade-off between these two measures.
Compared to the only other trade-off result [Alistarh, Gelashvili, Vojnovic;
PODC'15], we improve the number of interactions by almost a linear factor.
Furthermore, our protocols can be made uniform (working correctly without any
information on the population size $n$), yielding the first uniform majority
protocols that stabilize in a subquadratic number of interactions.
