Modular supervisory control of discrete-event systems

A modular approach to the supervisory control of a class of discrete-event systems is formulated, and illustrated with an example. Discrete-event systems are modeled by automata together with a mechanism for enabling and disabling a subset of state transitions. The basic problem of interest is to ensure by appropriate supervision that the closed loop behavior of the system lies within a given legal behavior. Assuming this behavior can be decomposed into an intersection of component restrictions, we determine conditions under which it is possible to synthesize the appropriate control in a modular fashion. The work of this author was supported by NSERC (Canada) under Grant No. A-7399. The work of this author was supported by the National Science Foundation through Grant No. ECS-8504584.     

CSP-i: An implementation of communicating sequential processes

Hoare's proposal for a notation for communicating sequential processes has led to the development of a number of concurrent languages based on the concept of message passing. CSP-i is a new language which reflects the design objectives of the original CSP notation more faithfully than most of these other languages. This paper describes the development of the language, as well as an implementation for a single processor, with simulated time-slicing providing pseudo-concurrency.     

Supervisory control of switching control systems

In this paper, the problem of designing a switching policy for an adaptive switching control system is formulated as a problem of supervisory control of a discrete-event system (DES). Two important problems in switching control are then addressed using the DES formulation and the theory of supervisory control under partial observation. First, it is verified whether for a given set of controllers, a switching policy satisfying a given set of constraints on the transitions among controllers exists. If so, then a minimally restrictive switching policy is designed. Next, an iterative algorithm is introduced for finding a minimal set of controllers for which a switching policy satisfying the switching constraints exists. It is shown that in the supervisory control problem considered in this paper, limitations on event observation are the factors that essentially restrict supervisory control. In other words, once observation limitations are respected, limitations on control will be automatically satisfied. This result is used to simplify the proposed iterative algorithm for finding minimal controller sets.     

A state-based approach to communicating processes

Communicating processes, which may exhibit nondeterministic behaviour, are specified as state-transition systems. Equivalence and refinement relations are defined in terms of the failures model of processes. Downward and upward simulation are considered as proof methods for refinement. Various operators on processes are defined and their refinement rules established. Mark Josephs joined the Programming Research Group at Oxford University in 1983, upon graduating from London University with a degree in Mathematics. One year later he was awarded the Master's degree in Computation. He received the doctorate in 1986 for his work in functional programming and took up a Visiting Scientist post at IBM Yorktown Heights in their Specification and Design Languages Group. He has now returned to the P.R.G. as a S.E.R.C. Research Officer.     

Multi-level hierarchical interface-based supervisory control

Hierarchical Interface-Based Supervisory Control employs interfaces that allow properties of a monolithic system to be verified through local analysis. By avoiding the need to verify properties globally, significant computational savings can be achieved. In this paper we provide local requirements for a multi-level architecture employing command-pair type interfaces. This multi-level architecture allows for a greater reduction in complexity and improved reconfigurability over the two-level case that has been previously studied since it allows the global system to be partitioned into smaller modules. This paper also provides results for synthesizing supervisors in the multi-level architecture that are locally maximally permissive with respect to a given specification and set of interfaces.     

Deadlock analysis in networks of communicating processes

We use the failures model of CSP to describe the behaviour of a class of networks of communicating processes. This model is well suited to reasoning about the deadlock potential of networks. We introduce a number of simple conditions on networks which aid deadlock analysis either by localizing the analysis required for a proof of deadlock-freedom or by restricting the circumstances in which deadlock could occur. In particular, we formulate some simple theorems which characterize the states in which deadlock can occur, and use them to prove some theorems on the absence of global deadlock in systems. We identify a special class of unidirectional networks and develop specialized results on their deadlock-freedom. We develop more general methods based on (at most) pairwise local deadlock analysis in networks, applicable to the large class of conflict-free networks. We introduce a methodology for proving deadlock-freedom in a large network by decomposing it into subnetworks which can be analysed separately. A variety of examples is given to show the utility of these results. We compare our work with earlier work by several other authors, and make some suggestions for future research. S.D. Brookes received a B.A. in mathematics (1978) and a D.Phil. in computer science (1983), both from Oxford University. His D. Phil supervisor was C.A.R. Hoare. He moved to Carnegie Mellon University in 1981, initially as a Research Computer Scientist and then (1984–1990) as an Assistant Professor in the School of Computer Science at CMU. He is currently an Associate Professor of Computer Science at CMU. His research interests include the mathematical foundations of programming languages, the theory of parallel and sequential computation, programming methodology, programming language design, and the development of semantically based logics for reasoning about program behavior. A.W. Roscoe received a B.A. in mathematics (1978) and a D.Phil. in computer science (1982), both from Oxford University. His D. Phil supervisor was C.A.R. Hoare. He was formerly a Junior Research Fellow at St Edmund Hall, Oxford (1980–1982) and the IBM Research Fellow of the Royal Society (1982–1983). Since 1983 he has been a University Lecturer in Computation at Oxford and a Fellow of University College. His research interests include the theory of parallel computing and its applications (e.g., to VLSI design), domain theory, distributed databases, general topology and the theory of image processing.This research was supported in part by funds from the Computer Science Department of Carnegie Mellon University, and by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 4976, monitored by the Air Force Avionics Laboratory under Contract F33615-87-C-1499. A.W. Roscoe gratefully acknowledges support by ONR Grant N00014-87-G-0242. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the offical policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the US Government.     

Bisimilarity enforcing supervisory control for deterministic specifications

This paper studies the supervisory control of nondeterministic discrete event systems to achieve a bisimulation equivalence between the controlled system and the deterministic specification. In particular, a necessary and sufficient condition is given for the existence of a bisimilarity enforcing supervisor, and a polynomial algorithm is developed to verify such a condition. When the existence condition holds, a bisimilarity enforcing supervisor is constructed. Otherwise, two methods are provided for synthesizing supremal feasible sub-specifications.     

Compiling communicating processes into delay-insensitive VLSI circuits

A method is described for compiling computations described as a set of communicating processes into VLSI circuits. The circuits obtained are delay-insensitive, i.e., their correct operation is independent of any assumption on delays in operators and wires, except that the delays are finite. They are also correct by construction since they are derived by a series of semantics-preserving transformation. Alain Martin is Professor of Computer Science at the California Institute of Technology. His research interests include programming methodology, in particular concurrent and distributed programming, and its application to the design of VLSI circuits and of highly concurrent computing systems.     

On the control of discrete-event dynamical systems

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Ramadge and Wonham, and we focus on the computational effort required for their solution. While the problem of supervisory control of a perfectly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when imperfectly observed systems are considered. Research supported by the Army Research Office (Grant No. DAAL03-86-K-0171) and by an NSF PYI award, with matching funds from Bellcore Inc.     

Denotational semantics of communicating processes based on a language for applicative multiprogramming

The denotational semantics of a simple language for describing tightly coupled ‘synchronous’ systems is defined by translating it into a language for applicative multiprogramming. The applicative language has originally been developed for describing nondeterministic stream-processing functions and loosely-coupled systems of communicating processes. Nevertheless, it can be used after very slight generalizations as a semantic target language for defining the meaning of programs representing tightly-coupled, synchronous systems.     

Trace,failure and testing equivalences for communicating processes

A basic question in the theory of communicating processes is “When should two processes be considered equivalent?”. Attempts to answer this question have led to the concepts of observation equivalence, bisimulations, testing equivalence, failure equivalence, etc. The main point of this paper is to increase the understanding and motivation for two of these equivalences, namely failure and testing equivalences. The approach starts with the idea that the equivalence of processes should be reducible to the visible sequences of actions which a process performs in various contexts. This idea is implemented by a string-based semantic order for communicating processes where divergence is catastrophic. Under some assumptions about contexts, the resulting semantics is shown to be equivalent to theimproved failure semantics of Brookes and Roscoe⁽¹⁾ and also to themust testing-semantics of Hennessy and DeNicola.^(2–4) This characterization gives independent support for the appropriateness of failures and testing.     

Exposure to deadlock for communicating processes is hard to detect

It is shown that the applicability of global state analysis as a tool for proving correctness of communication protocols is limited. Brand and Zafiropulo (1983) showed that reachability of global deadlock states for protocols with unbounded FIFO channels is undecidable. It is shown that the same is true for unbounded non-FIFO channels. For bounded FIFO channels the problem is shown to be PSPACE-hard.     

Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.     

Two implementation relations and the correctness of communicating replicated processes

This paper studies the correctness of distributed systems made up of replicated processes that communicate by message passing. Processes are described within the divergence model of CSP. The notion of correctness introduced is based on a relation that formally expresses the conformance of an implementation process with the target process it is intended to implement. A weak and a strong version of the relation are introduced, aimed at treating acyclic and cyclic process networks respectively. Both allow the study of (total) correctness and may cope with non-deterministic targets and implementations.We then show how a target process may be implemented (in the formal sense introduced) by replicating it in a set of copies, a majority of which is non-faulty.     

The transformation of collections of communicating sequential processes that represent pipeline configurations

The segments of a pipelined process can be represented as communicating sequential processes. The communication between the segments of the pipeline are represented as channel communication between the communicating sequential processes. It is possible to merge two communicating sequential processes (that would be adjacent in the pipeline) into one communicating sequential process. This is done by matching the output expressions of the first communicating sequential process (e.g. chlexpr) with the appropriate input expressions of the second communicating sequential process (e.g. ch?var) and replacing each pair by a single assignment statement (var = expr).     

Communicating parallel processes

By considering the problem of an event timer it is shown that the commonly available synchronizing facilities (monitors, CSP, distributed processes) are not able to always satisfactorily model the requirements of several processes which must run in parallel and which have to communicate with each other. The problem is discussed in general terms which show that what is required are new concepts for communicating processes. The synchronization facilities proposed are augmented to incorporate the concept of process scheduling directly from a process. This ensures that proper scheduling of process components can take place. The new mechanism is then applied to a number of the standard problems. It is also shown that the use of nondeterminacy in current facilities is probably not required and is, in fact, for many applications, a positive disadvantage.     

Towards models of tasks and task complexity in supervisory control applications

Dynamic task environments in supervisory control situations differ from those traditionally investigated in problem-solving research in that (1) several task goals exist in parallel, (2) task goals change dynamically as die behaviour of the technical process changes, and (3) information required to accomplish task goals changes across time. In the present work, it is suggested that such dynamic task environments can be described using two types of task goal networks, namely a control task goal (CTG) network and an information processing goal (IPG) network. CTG networks are generated by analysis of the operational states required to produce the commodity for which a technical system has been designed. For example, such analyses can be performed using approaches such as Mitchell's operator function model or canonical means-end analyses. IPG networks are generated by using the recenUy proposed functional information and knowledge acquisition (FIKA) modelling technique. Two examples from different domains illustrate how these task goal networks can be used to describe dynamic task environments. Finally, two different ways of using the task modelling approach are briefly discussed.     

The distributed simulation of clustered processes

An efficient method for use in the discrete-event distributed simulation of large systems is presented. A conservative distributed simulation as well as the mapping of several simulated processes onto the same processor is assumed. The method consits of two algorithms: an algorithm for computing the lower bounds on times of future events, and a distributed algorithm that resolves deadlocks. The performance of the method is demonstrated by comparing it to the Chandy-Misra-Bryant simulation and by presenting some experimental results. Bojan Groelj received his B.EE. and M.EE. degrees from the University of Ljubljana, Slovenia (Yugoslavia), in 1978 and 1981, respectively. His Ph.D. degree in Computer Science is from McGill University, Montreal, Canada (1988). In 1988, he joined the Center for Advanced Computer Studies, University of Southwestern Louisiana, where he is currently an Assistant Professor. His current research interests include distributed simulation, distributed computing in general, program proving, and sorting. For the last two years, the author has been proving a distributed deadlock-detection algorithm using the UNITY approach. Carl Tropper is an Associate Professor of Computer Science at McGill University, Montreal, Canada. His major area of research at present is distributed discrete-event simulation. He has also worked in the area of performance evaluation of computer networks. Formerly, he was with BBN Communications Corporation, Cambridge, Mass., where he contributed to the design and evaluation of various widearea network protocols.This research was supported in part by the National Science Foundation under Grant CCR-8909098. An extended version of this work will appear in Progress in Simulation, vol. II, Ablex Publishing Corporation     

The quality control chart for monitoring multivariate autocorrelated processes

Previously, quality control and improvement researchers discussed multivariate control charts for independent processes and univariate control charts for autocorrelated processes separately. We combine the two topics and propose vector autoregressive (VAR) control charts for multivariate autocorrelated processes. In addition, we estimate AR(p) models instead of ARMA models for the systematic cause of variation. We discuss the procedures to construct the VAR chart. We examine the effects of parameter shifts and by example present procedures to show the feasibility of VAR control charts. We simulate the average run length to assess the performance of the chart.     

Suboptimal supervisory control of Petri nets in presence of uncontrollable transitions via monitor places

This paper deals with the problem of enforcing generalized mutual exclusion constraints (GMEC) on place/transition nets with uncontrollable transitions. An efficient control synthesis technique, which has been proposed in the literature, enforces GMEC constraints by introducing monitor places to create suitable place invariants. The method has been shown to be maximally permissive and to give a unique control structure in the case that the set of legal markings is controllable. This paper investigates on and formally shows that the class of controllers obtained by this technique may not have a supremal element for uncontrollable specifications. Moreover, it is shown that the family of monitor places enforcing an uncontrollable specification can be parameterized with respect to the solution of a linear system of equation. An algorithm to obtain such parameterization is presented here.