  Population protocols are a formal model of computation by identical,
anonymous mobile agents interacting in pairs. Their computational power is
rather limited: Angluin et al. have shown that they can only compute the
predicates over $\mathbb{N}^k$ expressible in Presburger arithmetic. For this
reason, several extensions of the model have been proposed, including the
addition of devices called cover-time services, absence detectors, and clocks.
All these extensions increase the expressive power to the class of predicates
over $\mathbb{N}^k$ lying in the complexity class NL when the input is given in
unary. However, these devices are difficult to implement, since they require
that an agent atomically receives messages from all other agents in a
population of unknown size; moreover, the agent must know that they have all
been received. Inspired by the work of the verification community on Emerson
and Namjoshi's broadcast protocols, we show that NL-power is also achieved by
extending population protocols with reliable broadcasts, a simpler, standard
communication primitive.
