  The traditional models of distributed computing focus mainly on networks of
computer-like devices that can exchange large messages with their neighbors and
perform arbitrary local computations. Recently, there is a trend to apply
distributed computing methods to networks of sub-microprocessor devices, e.g.,
biological cellular networks or networks of nano-devices. However, the
suitability of the traditional distributed computing models to these types of
networks is questionable: do tiny bio/nano nodes "compute" and/or "communicate"
essentially the same as a computer? In this paper, we introduce a new model
that depicts a network of randomized finite state machines operating in an
asynchronous environment. Although the computation and communication
capabilities of each individual device in the new model are, by design, much
weaker than those of a computer, we show that some of the most important and
extensively studied distributed computing problems can still be solved
efficiently.
