On the number of binary-minded individuals required to compute

We recently obtained partial results on the computational power of population protocols when the population is assumed to be large.We studied in particular a particular protocol that we proved to converge towards , using weak-convergence methods for stochastic processes.In this paper, we prove that it is possible to compute with precision ϵ>0 in a time polynomial in using a number of agents polynomial in , with individuals that can have only two states.This is established through a general result on approximation of stochastic differential equations by a stochastic Euler-like discretization algorithm, of general interest.