Robust asynchronous protocols are finite-state

Mukund, Madhavan ; Narayan Kumar, K. ; Radhakrishnan, Jaikumar ; Sohoni, Milind (1998) Robust asynchronous protocols are finite-state Lecture Notes in Computer Science, 1443 . pp. 188-199. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/index/V1362G850UX73157...

Related URL: http://dx.doi.org/10.1007/BFb0055052

Abstract

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.

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

Repository Staff Only: item control page