M Mukund, K Narayan Kumar, J Radhakrishnan and M Sohoni

*Report TCS-97-4*,
SPIC Mathematical Institute, Madras,
India (1997)

This paper is a step towards developing a new automata-theoretic framework for describing distributed finite-state systems with asynchronous communication. If we assume that messages can be delayed arbitrarily in transit, it is reasonable to model the global behaviour of such systems in terms of finite-state automata equipped with blind counters---that is, counters which cannot be tested for zero.

We analyse the languages accepted by such automata and show that it is decidable whether the language of such an automaton is empty. We also develop a variety of pumping lemmas which can be used to show that certain languages are not accepted by these automata.

Our main result is that the subclass of languages
accepted by these automata which is closed under
complementation is precisely the class of regular languages.
In the context of asynchronous protocols, our result implies
that robust finite-state protocols use bounded buffers. In
other words, messages are used *only* for
hand-shaking---that is, for coordinating the interaction
between different processes and the environment.

It is well known that automata with blind counters are
closely related to Petri nets. However, our definition of
languages is more appropriate for reasoning about
asynchronous communication and is *different* from the
definition used in the theory of Petri nets.

- Download PDF.