  The density classification problem is the computational problem of finding
the majority in a given array of votes in a distributed fashion. It is known
that no cellular automaton rule with binary alphabet can solve the density
classification problem. On the other hand, it was shown that a probabilistic
mixture of the traffic rule and the majority rule solves the one-dimensional
problem correctly with a probability arbitrarily close to one. We investigate
the possibility of a similar approach in two dimensions. We show that in two
dimensions, the particle spacing problem, which is solved in one dimension by
the traffic rule, has no cellular automaton solution. However, we propose exact
and randomized solutions via interacting particle systems. We assess the
performance of our models using numeric simulations.
