  We give a simple characterization of which functions can be computed
deterministically by anonymous processes in dynamic networks, depending on the
number of leaders in the network. In addition, we provide efficient distributed
algorithms for computing all such functions assuming minimal or no knowledge
about the network. Each of our algorithms comes in two versions: one that
terminates with the correct output and a faster one that stabilizes on the
correct output without explicit termination. Notably, these are the first
deterministic algorithms whose running times scale linearly with both the
number of processes and a parameter of the network which we call "dynamic
disconnectivity" (meaning that our dynamic networks do not necessarily have to
be connected at all times). We also provide matching lower bounds, showing that
all our algorithms are asymptotically optimal for any fixed number of leaders.
  While most of the existing literature on anonymous dynamic networks relies on
classical mass-distribution techniques, our work makes use of a recently
introduced combinatorial structure called "history tree", also developing its
theory in new directions. Among other contributions, our results make
definitive progress on two popular fundamental problems for anonymous dynamic
networks: leaderless Average Consensus (i.e., computing the mean value of input
numbers distributed among the processes) and multi-leader Counting (i.e.,
determining the exact number of processes in the network). In fact, our
approach unifies and improves upon several independent lines of research on
anonymous networks, including Nedic et al., IEEE Trans. Automat. Contr. 2009;
Olshevsky, SIAM J. Control Optim. 2017; Kowalski-Mosteiro, ICALP 2019, SPAA
2021; Di Luna-Viglietta, FOCS 2022.
