Madhavan Mukund


Robust Asynchronous Protocols Are Finite-State

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

Proc. ICALP '98, Springer LNCS 1443 (1998) 188-199.

© Springer-Verlag Berlin Heidelberg

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.

  • Download PDF.