Towards a characterisation of finite-state message-passing systems

Mukund, Madhavan ; Narayan Kumar, K. ; Radhakrishnan, Jaikumar ; Sohoni, Milind (1998) Towards a characterisation of finite-state message-passing systems Lecture Notes in Computer Science, 1538 . pp. 282-299. ISSN 0302-9743

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:89518
Deposited On:27 Apr 2012 13:36
Last Modified:27 Apr 2012 13:36

Repository Staff Only: item control page