Record Details

Towards a characterisation of finite-state message-passing systems

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Towards a characterisation of finite-state message-passing systems
 
Creator MUKUND, M
KUMAR, KN
RADHAKRISHNAN, J
SOHONI, M
 
Description 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.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T12:50:26Z
2011-12-15T09:11:09Z
2011-10-23T12:50:26Z
2011-12-15T09:11:09Z
1998
 
Type Article; Proceedings Paper
 
Identifier ADVANCES IN COMPUTING SCIENCE-ASIAN' 98,1538,282-299
3-540-65388-0
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15133
http://hdl.handle.net/100/1888
 
Source 4th Asian Computing Science Conference (ASIAN 98),MANILA, PHILIPPINES,DEC 08-10, 1998
 
Language English