Information partitions, deadlock, and non-sequential stochastic control
Mark S. Andersland, Demosthenis Teneketzis · 2005
In control theory it is often assumed that a system's inputs and outputs can be ordered a priori in time. In practice, many distributed systems (those subject to deadlock, for instance) are not sequential in this sense. As a consequence, the task of identifying good designs is difficult to formulate as a stochastic control problem, e.g., nonsequential designs need not possess expected rewards. A property of a design's information partition that is necessary and sufficient to ensure deadlock-freeness is identified and shown to ensure that the design possesses an expected reward. This analysis, which suggests a framework for the constrained optimization of nonsequential stochastic control problems, is motivated by the fact, established in this work, that there exist deadlock-free designs that cannot be associated with any deadlock information structure.>