@article{AAEGR16,
  Author    = {Dan Alistarh and
               James Aspnes and
               David Eisenstat and
               Rati Gelashvili and
               Ronald L. Rivest},
  title     = {Time-Space Trade-offs in Population Protocols},
  journal   = {CoRR},
  volume    = {abs/1602.08032},
  date      = { 2016-02-25 },                  
  OPTyear   = { 2016 },
  OPTmonth  = { February 25, },
  url       = { http://arxiv.org/abs/1602.08032 },
  timestamp = { Tue, 01 Mar 2016 17:47:25 +0100 },
  biburl    = { http://dblp.uni-trier.de/rec/bib/journals/corr/AlistarhAEGR16 },
  bibsource = { dblp computer science bibliography, http://dblp.org },
  abstract =  { Population protocols are a popular model of
                  distributed computing, in which randomly-interacting
                  agents with little computational power cooperate to
                  jointly perform computational tasks. Inspired by
                  developments in molecular computation, and in
                  particular DNA computing, recent algorithmic work
                  has focused on the complexity of solving simple yet
                  fundamental tasks in the population model, such as
                  leader election (which requires stabilization to a
                  single agent in a special "leader" state), and
                  majority (in which agents must stabilize to a
                  decision as to which of two possible initial states
                  had higher initial count). Known results point
                  towards an inherent trade-off between the time
                  complexity of such algorithms, and the space
                  complexity, i.e. size of the memory available to
                  each agent.  In this paper, we explore this
                  trade-off and provide new upper and lower bounds for
                  majority and leader election. First, we prove a
                  unified lower bound, which relates the space
                  available per node with the time complexity
                  achievable by a protocol: for instance, our result
                  implies that any protocol solving either of these
                  tasks for $n$ agents using $O( \log \log n )$ states
                  must take $\Omega( n / \rm{polylog} n )$ expected
                  time. This is the first result to characterize time
                  complexity for protocols which employ super-constant
                  number of states per node, and proves that fast,
                  poly-logarithmic running times require protocols to
                  have relatively large space costs.  On the positive
                  side, we give algorithms showing that fast,
                  poly-logarithmic stabilization time can be achieved
                  using $O( \log^2 n )$ space per node, in the case of
                  both tasks. Overall, our results highlight a time
                  complexity separation between $O(\log \log n)$ and
                  $\Theta( \log^2 n )$ state space size for both
                  majority and leader election in population
                  protocols, and introduce new techniques, which
                  should be applicable more broadly.  },
  note =         { (version 7: April 17, 2017) },
}