CONCUR: A language for continuous, concurrent processes

Hendrix's robot modeling system presented a simulation method in which time is represented as a continuous phenomenon. This paper introduces the language CONCUR, which realizes Hendrix's concept through an extension of the LISP environment. CONCUR uses generalized procedures (scenarios) operating in a data-driven mode to implement Hendrix's events. The heart of CONCUR is a generalized pattern-matcher which permits operators within the patterns to bind variables and modify the match process. We include several detailed examples in addition to an implementation of the pattern matcher.     

Evolvable concurrent processes

This paper presents a formal model of concurrent processes whose functions can be modified from the environments during execution. In many applications, it takes too much cost to stop the whole of the concurrent system working in distributed environments to update its components. Features of dynamic evolution that make it possible to modify functions of processes without termination are important. In this paper, a formal model of evolvable concurrent processes is presented using logical formulas of linear logic. The operational semantics is defined using a formal proof in a fragment of the sequent calculus of linear logic. A method for replacing the continuations of working processes by applications of inference rules of linear logic is presented.     

Towards a language for concurrent processes

In this paper we shall discuss concurrency in programming languages, with a view towards designing a process-oriented language which, by its inherent parallelism, is well suited to exploit the forthcoming generation of distributed processor networks. We shall start by discussing the traditional approach towards managing concurrency, with ‘monitors’ co-ordinating the interactions of ‘processes’, and shall demonstrate that this approach actually degrades concurrency by imposing sequentiality during interactions because it is based on the premise of co-ordinating secure access to shared resources. As a tool for interprocess communication it is felt that the ‘monitor’ is too far removed from the abstract nature of the problem, and so, as a purely engineering solution, it imposes too broad and too prolonged an exclusion to be acceptable in general. Instead we turn to a simpler, and ultimately more powerful notion of ‘message passing’ between parallel processes. We shall show how, if the message system is polymorphic, any data value, however large it is, can pass freely between any pair of processes. By making the processes themselves values in the language we shall discover that message networks can come into being dynamically, and tailor themselves to their applications as and when necessary by ‘short-circuiting’ extensive communications paths. We shall also see how, if the message system is inherently asynchronous, the degree of the parallelism in a system can be enhanced, not degraded, as more and elaborate communications paths develop, the only sequentiality in the system as a whole being imposed by synchronizing processes, not the message passing system itself. After discussing the various built-in system facilities that permit processes to dynamically find out about and study one another, thus permitting processes to set up and thereafter supervise whole subsystems, we shall round off by discussing the advantages of introducing the machines themselves into the language, making it possible for processes to become aware of, and then ‘migrate’ within, the topological structure of a multi-processor distributed network, moving closer to their application, or just to a less-loaded processor, as the need arises. To conclude we shall contrast this new-style process-oriented language with various existing programming languages which have experimented with concurrency, either implicitly or explicitly, in order to see if, and if so how, this new style is any simpler and more powerful than its precursors.     

A proof system for concurrent ADA programs

A subset of ADA is introduced, ADA-CF, to study the basic synchronization and communication primitive of ADA, the rendezvous. Basing ourselves on the techniques introduced by Apt, Francez and de Roever for their CSP proof system, we develop a Hoare-style proof system for proving partial correctness properties which is sound and relatively complete. The proof system is then extended to deal with safety, deadlock, termination and failure. No prior exposure of the reader to parallel program proving techniques is presupposed. Two non-trivial example proofs are given of ADA-CF programs; the first one concerns a buffered producer-consumer algorithm, the second one a parallel sorting algorithm due to Brinch Hansen. Features of ADA expressing dynamic process creation and realtime constraints are not covered by our proof methods. Consequently, we do not claim that the methods described can be extended to full ADA without serious additional further research.     

Correctness of concurrent processes

A new notion of correctness for concurrent processes is introduced and investigated. It is a relationship P sat S between process terms P built up from operators of CCS [24], CSP [18] and COSY [20] and logical formulas S specifying sets of finite communication sequences as in [38]. The definition of P sat S is based on a Petri net semantics for process terms [27]. The main point is that P sat S requires a simple liveness property of the net denoted by P. This implies that P is divergence free and externally deterministic. Process correctness P sat S determines a new semantic model for process terms and logical formulas. It is a modification ^* of the readiness semantics [28] which is fully abstract with respect to the relation P sat S. The model ^* abstracts from the concurrent behaviour of process terms and certain aspects of their internal activity. In ^* process correctness P sat S boils down to semantic equality: ^*P = ^*S. The modified readiness equivalence is closely related to failure equivalence [7] and strong testing equivalence [9].     

A hybrid system for SPC concurrent pattern recognition

Any nonrandom patterns shown in Statistical Process Control (SPC) charts imply possible assignable causes that may deteriorate the process performance. Hence, timely detecting and recognizing Control Chart Patterns (CCPs) for nonrandomness is very important in the implementation of SPC. Due to the limitations of run-rule-based approaches, Artificial Neural Networks (ANNs) have been resorted for detecting CCPs. However, most of the reported ANN approaches are only limited to recognize single basic patterns. Different from these approaches, this paper presents a hybrid approach by integrating wavelet method with ANNs for on-line recognition of CCPs including concurrent patterns. The main advantage of this approach is its capability of recognizing coexisted or concurrent patterns without training by concurrent patterns. The test results using simulated data have demonstrated the improvements and the effectiveness of the methodology with a success rate up to 91.41% in concurrent CCP recognition.     

A concurrent engineering constraint-based system

This research article demonstrates the use of constraint networks for modelling the knowledge which is necessary for concurrent product and process design. A knowledge-based constraint network system has been developed to maintain design consistency and to support the selection of appropriate manufacturing processes according to pre-defined constraints. A number of constraints related to existing manufacturing facilities and expertise are formulated and modelled using the rules of the knowledge-based toolkit. These constraints are implemented to identify the appropriate machining processes and to show the feasibility of a product's design as it progresses and before making the final prototype. The combination of design and manufacturing constraints enables designers to examine whether the designed part can be manufactured with the available manufacturing facilities.     

A system architecture for fault tolerance in concurrent software

A system architecture called the recovery metaprogram (RMP) is proposed. It separates the application from the recovery software, giving programmers a single environment that lets them use the most appropriate fault-tolerance scheme. To simplify the presentation of the RMP approach, it is assumed that the fault model is limited to faults originating in the application software, and that the hardware and kernel layers can mask their own faults from the RMP. Also, relationships between backward and forward error recovery are not considered. Some RMP examples are given, and a particular RMP implementation is described     

A proof system for distributed processes

Summary A partial correctness proof system for Brinch Hansen's Distributed Processes (DP) is presented. Two important aspects of the system are: Proofs of individual processes of a DP program are completely isolated from each other; in particular, no assumptions are allowed in the proof of one process about the behavior of the other processes. Secondly a process is characterized by its externally visible behavior, i.e. the sequence of interactions between this process and the other processes of the program. An example demonstrates the use of the system.This paper is an extended version of a paper presented at the Workshop on Logics of Programs, Brooklyn, New York, June 17–19, 1985 and was supported in part by the National Science Foundation under grant ECS-8404725     

A proof system for distributed processes

Summary A partial correctness proof system for Brinch Hansen’s Distributed Processes (DP) is presented. Two important aspects of the system are: Proofs of individual processes of a DP program are completely isolated from each other; in particular, no assumptions are allowed in the proof of one process about the behavior of the other processes. Secondly a process is characterized by its externally visible behavior, i.e. the sequence of interactions between this process and the other processes of the program. An example demonstrates the use of the system. This paper is an extended version of a paper presented at the Workshop on Logics of Programs, Brooklyn, New York, June 17–19, 1985 and was supported in part by the National Science Foundation under grant ECS-8404725.     

A system for design and concurrent engineering under imprecision

This paper proposes an approach to handling imprecision in design and concurrent engineering systems by using interval analysis and constraint networks. By allowing design parameters to be specified with intervals rather than exact points, this approach permits designers to iteratively transform vague conceptual designs into detailed final designs. When a designer changes a variable's interval or assigns a value, the results are propagated through constraints and the resulting feasible interval for all other dependent variables is pruned. The interval constraint network approach described in this paper extends previous work by allowing the representation of and reasoning about complex constraints involving conditions, conjunctions and disjunctions, as well as both symbolic and numeric variables. Many concurrent engineering constraints cannot be modeled without this sort of representational flexibility. A prototype of this approach has been implemented in a system called SPARK-IP. The operation of SPARK-IP is demonstrated through a concurrent engineering design problem involving printed wiring boards.     

A concurrent engineering approach to selective implementation of alternative processes

During the last decade, integration between design and manufacturing has shown to be a major competitive weapon and much research work has been carried out about considering at the product design stage production process issues.Most of the literature on such techniques focuses on integrating the design of a product and the design of its manufacturing processes, disregarding issues related to the design and management of the manufacturing system. Nonetheless, decisions taken at the product and process design stage could have an influence on typical production planning and control issues such as, for example, minimising lead times and maximising machine utilisation.Many research works show the advantage of a higher process flexibility, in terms of machine utilisation, manufacturing lead time, inventory level, and the like (see, for example, Tsubone and Horikawa, The International Journal of Flexible Manufacturing Systems 11 (1999) 83 or Ferreira and Wysk, Journal of Manufacturing System 19 (2001)), but developing alternative machine possibility has a cost that is not negligible (International Journal of Production Economics 48 (1997) 237). Therefore, guidelines are needed for identifying for what items and for which operations to develop alternative processes.In this paper, the relationship between alternative processes availability and manufacturing system performances are investigated, showing that the advantage of additional alternative process decreases as the number of alternatives increases, and that given a certain number of alternative processes developed, there is a strong difference in performances depending on what alternative processes have been implemented. Then a new procedure is presented for guiding in selecting for which operations to implement alternative processes in order to maximise the flexibility advantages limiting the implementation cost.The proposed procedure is then tested, under different operating conditions, against a practical rule by means of a simulation model.     

A logic-based transformation system

In spite of advances in various transformation systems the transformation of a nonmonotonic-logic-based requirements specification into a procedural (imperative) language program has not been investigated. This paper presents a logic-based transformation system that can transform a nonmonotonic-logic-based specification, the Frame-and-Rule Oriented Requirement Specification Language (FRORL), into procedural language programs. We discuss how to handle nonmonotonic inheritance in FRORL and then establish a matrix-based data flow and dependency analysis mechanism to find all the possible data transformation paths in a logic-based specification. Using a newly developed algorithm, we can adjust the execution sequence of a logic-based specification so that the functions included in the logic-based specification can be represented by a sequential procedural language program     

A decision support system for product design in concurrent engineering

Compared with the traditional sequential design method, concurrent engineering is a systematic approach to integrate concurrent design of products and their related processes. One of the key factors to successfully implement concurrent engineering is information technology. In order to design a product and its manufacturing process simultaneously, information on product features, manufacturing requirements, and customer demands must be processed while the design is concurrently going on. There is an increased understanding of the importance of the correct decisions being made at the conceptual design and development stages that involve many complex evaluation and decision-making tasks. In order to promote the efficiency in concurrent product development, appropriate evaluation and decision tools need to be provided. In this paper, the characteristics of fuzzy, multi-stage evaluation and decision making in concurrent product development process are analyzed and a decision support system for product design in concurrent engineering is presented. An example is given to illustrate the application of the system.     

A verification system for concurrent programs based on the Boyer-Moore prover

We describe a mechanical proof system for concurrent programs, based on a formalization of the temporal framework of Manna and Pnueli as an extension of the computational logic of Boyer and Moore. The system provides a natural representation of specifications of concurrent programs as temporal logic formulas, which are automatically translated into terms that are subject to verification by the Boyer-Moore prover. Several specialized derived rules of inference are introduced to the prover in order to facilitate the verification of invariance (safety) and eventuality (liveness) properties. The utility of the system is illustrated by a correctness proof for a two-process program that computes binomial coefficients.     

A WSDL-based type system for asynchronous WS-BPEL processes

We tackle the problem of providing rigorous formal foundations to current software engineering technologies for web services, and especially to WSDL and WS-BPEL, two of the most used XML-based standard languages for web services. We focus on a simplified fragment of WS-BPEL sufficiently expressive to model asynchronous interactions among web services in a network context. We present this language as a process calculus-like formalism, that we call ws-calculus, for which we define an operational semantics and a type system. The semantics provides a precise operational model of programs, while the type system forces a clean programming discipline for integrating collaborating services. We prove that the operational semantics of ws-calculus and the type system are ‘sound’ and apply our approach to some illustrative examples. We expect that our formal development can be used to make the relationship between WS-BPEL programs and the associated WSDL documents precise and to support verification of their conformance.     

Modeling concurrent real-time processes using discrete events

We give a formal framework for studying real-time discrete-event systems. It describes concurrent processes as sets of possible behaviors. Compositions of processes are processes with behaviors in the intersection of the behaviors of the component processes. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags denote time. Zeno conditions are defined and methods are given for avoiding them. Strict causality ensures determinacy under certain technical conditions, and delta-causality ensures the absence of Zeno conditions. This revised version was published online in June 2006 with corrections to the Cover Date.