  This work concerns the general issue of combined optimality in terms of time
and space complexity. In this context, we study the problem of (exact) counting
resource-limited and passively mobile nodes in the model of population
protocols, in which the space complexity is crucial. The counted nodes are
memory-limited anonymous devices (called agents) communicating asynchronously
in pairs (according to a fairness condition). Moreover, we assume that these
agents are prone to failures so that they cannot be correctly initialized. This
study considers two classical fairness conditions, and for each we investigate
the issue of time optimality of counting given the optimal space per agent. In
the case of randomly interacting agents (probabilistic fairness), as usual, the
convergence time is measured in terms of parallel time (or parallel
interactions), which is defined as the number of pairwise interactions until
convergence, divided by n (the number of agents). In case of weak fairness,
where it is only required that every pair of agents interacts infinitely often,
the convergence time is defined in terms of non-null transitions, i.e, the
transitions that affect the states of the interacting agents.First, assuming
probabilistic fairness, we present a "non-guessing" time optimal protocol of
O(n log n) expected time given an optimal space of only one bit, and we prove
the time optimality of this protocol. Then, for weak fairness, we show that a
space optimal (semi-uniform) solution cannot converge faster than in
$\Omega$(2^n) time (non-null transitions). This result, together with the time
complexity analysis of an already known space optimal protocol, shows that it
is also optimal in time (given the optimal space constrains).
