Record Details

Robust asynchronous protocols are finite-state

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Robust asynchronous protocols are finite-state
 
Creator MUKUND, M
KUMAR, KN
RADHAKRISHNAN, J
SOHONI, M
 
Subject regular languages
systems
 
Description We consider networks of finite-state machines which communicate over reliable channels which may reorder messages. Each machine in the network also has a local input tape. Since channels are unbounded, the network as a whole is, in general, infinite-state. An asynchronous protocol is a network equipped with an acceptance condition. Such a protocol is said to be robust if it never deadlocks and, moreover, it either accepts or rejects each input in an unambiguous manner. The behaviour of a. robust protocol is insensitive to nondeterminism introduced by either message reordering or the relative speeds at which components read their local inputs. Using an automata-theoretic model, we show that, at a global level, every robust asynchronous protocol has a finite-state representation To prove this, we establish a variety of pumping lemmas. We also demonstrate a distributed language which does not admit a robust protocol.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T12:44:19Z
2011-12-15T09:11:09Z
2011-10-23T12:44:19Z
2011-12-15T09:11:09Z
1998
 
Type Article; Proceedings Paper
 
Identifier AUTOMATA, LANGUAGES AND PROGRAMMING,1443,188-199
3-540-64781-3
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15132
http://hdl.handle.net/100/1887
 
Source 25th International Colloquium on Automata, Languages and Programming (ICALP 98),AALBORG, DENMARK,JUL 13-17, 1998
 
Language English