Asynchronous implementation of synchronous discrete event control

Discrete event control is typically designed under the synchronous hypothesis that sensing and actuation incur zero delays, i.e., there exists zero delay between an event execution at a plant site and its observation at a controller site, and also between a control computation at a controller site and its enforcement at a plant site. An actual implementation, however, is asynchronous, introducing delays in sensing as well as actuation. A natural question that arises is what additional property must a given specification satisfy so that it remains implementable in spite of the delays introduced by an underlying asynchronous implementation platform. We formulate the problem of asynchronous implementation of synchronous control when both the sensing and actuation delays are bounded. We introduce the notion of bounded-delay asynchronous composition to characterize the behavior of a controlled plant when the sensing and actuation delays are bounded. We introduce the notion of bounded-delay implementability and show that this together with the existence conditions of the synchronous setting (namely controllability, closure, and nonemptiness) serves as a necessary and sufficient condition for the existence of a controller so that the controlled behavior under the asynchronous implementation remains the same as that under the synchronous implementation. We present an algorithm for checking the property of bounded-delay implementability, whose complexity is linear (resp., quadratic) in the size of the plant (resp., specification), and exponential in the delay bounds. We also examine the lattice structure of a set of bounded-delay implementable languages, and show its non-closure under union whereas closure under union over an increasing chain and intersection.