  We give the first linear-time counting algorithm for processes in anonymous
1-interval-connected dynamic networks with a leader. As a byproduct, we are
able to compute in $3n$ rounds every function that is deterministically
computable in such networks. If explicit termination is not required, the
running time improves to $2n$ rounds, which we show to be optimal up to a small
additive constant (this is also the first non-trivial lower bound for
counting). As our main tool of investigation, we introduce a combinatorial
structure called "history tree", which is of independent interest. This makes
our paper completely self-contained, our proofs elegant and transparent, and
our algorithms straightforward to implement.
  In recent years, considerable effort has been devoted to the design and
analysis of counting algorithms for anonymous 1-interval-connected networks
with a leader. A series of increasingly sophisticated works, mostly based on
classical mass-distribution techniques, have recently led to a celebrated
counting algorithm in $O({n^{4+ \epsilon}} \log^{3} (n))$ rounds (for
$\epsilon>0$), which was the state of the art prior to this paper. Our
contribution not only opens a promising line of research on applications of
history trees, but also demonstrates that computation in anonymous dynamic
networks is practically feasible, and far less demanding than previously
conjectured.
