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

*Proc. ASIAN '98*, Springer LNCS 1538 (1998) 282-299.

*© Springer-Verlag Berlin Heidelberg*

We investigate an automata-theoretic model of distributed
systems which communicate via message-passing. Each node in
the system is a finite-state device. Channels are assumed to
be reliable but may deliver messages out of order. Hence,
each channel is modelled as a set of counters, one for each
type of message. These counters may *not* be tested
for zero.

Though each node in the network is finite-state, the overall system is potentially infinite-state because the counters are unbounded. We work in an interleaved setting where the interactions of the system with the environment are described as sequences. The behaviour of a system is described in terms of the language which it accepts---that is, the set of valid interactions with the environment that are permitted by the system.

Our aim is to characterise the class of message-passing systems whose behaviour is finite-state. Our main result is that the language accepted by a message-passing system is regular if and only if both the language and its complement are accepted by message-passing systems. We also exhibit an alternative characterisation of regular message-passing languages in terms of deterministic automata.

- Download PDF.
- Technical report with more details.