  In this work, we initiate the study of \emph{smoothed analysis} of population
protocols. We consider a population protocol model where an adaptive adversary
dictates the interactions between agents, but with probability $p$ every such
interaction may change into an interaction between two agents chosen uniformly
at random. That is, $p$-fraction of the interactions are random, while
$(1-p)$-fraction are adversarial. The aim of our model is to bridge the gap
between a uniformly random scheduler (which is too idealistic) and an
adversarial scheduler (which is too strict).
  We focus on the fundamental problem of leader election in population
protocols. We show that, for a population of size $n$, the leader election
problem can be solved in $O(p^{-2}n \log^3 n)$ steps with high probability,
using $O((\log^2 n) \cdot (\log (n/p)))$ states per agent, for \emph{all}
values of $p\leq 1$. Although our result does not match the best known running
time of $O(n \log n)$ for the uniformly random scheduler ($p=1$), we are able
to present a \emph{smooth transition} between a running time of $O(n \cdot
\mathrm{polylog} n)$ for $p=1$ and an infinite running time for the adversarial
scheduler ($p=0$), where the problem cannot be solved. The key technical
contribution of our work is a novel \emph{phase clock} algorithm for our model.
This is a key primitive for much-studied fundamental population protocol
algorithms (leader election, majority), and we believe it is of independent
interest.
