  Broadcast consensus protocols (BCPs) are a model of computation, in which
anonymous, identical, finite-state agents compute by sending/receiving global
broadcasts. BCPs are known to compute all number predicates in
$\mathsf{NL}=\mathsf{NSPACE}(\log n)$ where $n$ is the number of agents. They
can be considered an extension of the well-established model of population
protocols. This paper investigates execution time characteristics of BCPs. We
show that every predicate computable by population protocols is computable by a
BCP with expected $\mathcal{O}(n \log n)$ interactions, which is asymptotically
optimal. We further show that every log-space, randomized Turing machine can be
simulated by a BCP with $\mathcal{O}(n \log n \cdot T)$ interactions in
expectation, where $T$ is the expected runtime of the Turing machine. This
allows us to characterise polynomial-time BCPs as computing exactly the number
predicates in $\mathsf{ZPL}$, i.e. predicates decidable by log-space bounded
randomised Turing machine with zero-error in expected polynomial time where the
input is encoded as unary.
