  Population protocols have been introduced by Angluin et al. as a model in
which n passively mobile anonymous finite-state agents stably compute a
predicate on the multiset of their inputs via interactions by pairs. The model
has been extended by Guerraoui and Ruppert to yield the community protocol
models where agents have unique identifiers but may only store a finite number
of the identifiers they already heard about. The population protocol models can
only compute semi-linear predicates, whereas in the community protocol model
the whole community of agents provides collectively the power of a Turing
machine with a O(n log n) space. We consider variations on the above models and
we obtain a whole landscape that covers and extends already known results: By
considering the case of homonyms, that is to say the case when several agents
may share the same identifier, we provide a hierarchy that goes from the case
of no identifier (i.e. a single one for all, i.e. the population protocol
model) to the case of unique identifiers (i.e. community protocol model). We
obtain in particular that any Turing Machine on space O(logO(1) n) can be
simulated with at least O(logO(1) n) identifiers, a result filling a gap left
open in all previous studies. Our results also extend and revisit in particular
the hierarchy provided by Chatzigiannakis et al. on population protocols
carrying Turing Machines on limited space, solving the problem of the gap left
by this work between per-agent space o(log log n) (proved to be equivalent to
population protocols) and O(log n) (proved to be equivalent to Turing
machines).
