  Population protocols are a model of distributed computing, in which $n$
agents with limited local state interact randomly, and cooperate to
collectively compute global predicates. An extensive series of papers, across
different communities, has examined the computability and complexity
characteristics of this model. Majority, or consensus, is a central task, in
which agents need to collectively reach a decision as to which one of two
states $A$ or $B$ had a higher initial count. Two complexity metrics are
important: the time that a protocol requires to stabilize to an output
decision, and the state space size that each agent requires.
  It is known that majority requires $\Omega(\log \log n)$ states per agent to
allow for poly-logarithmic time stabilization, and that $O(\log^2 n)$ states
are sufficient. Thus, there is an exponential gap between the upper and lower
bounds.
  We address this question. We provide a new lower bound of $\Omega(\log n)$
states for any protocol which stabilizes in $O( n^{1-c} )$ time, for any $c >
0$ constant. This result is conditional on basic monotonicity and output
assumptions, satisfied by all known protocols. Technically, it represents a
significant departure from previous lower bounds. Instead of relying on dense
configurations, we introduce a new surgery technique to construct executions
which contradict the correctness of algorithms that stabilize too fast.
Subsequently, our lower bound applies to general initial configurations.
  We give an algorithm for majority which uses $O(\log n)$ states, and
stabilizes in $O(\log^2 n)$ time. Central to the algorithm is a new leaderless
phase clock, which allows nodes to synchronize in phases of $\Theta(n \log{n})$
consecutive interactions using $O(\log n)$ states per node. We also employ our
phase clock to build a leader election algorithm with $O(\log n )$ states,
which stabilizes in $O(\log^2 n)$ time.
