General Reversibility

The first and the second author introduced reversible CCS (RCCS) in order to model concurrent computations where certain actions are allowed to be reversed. Here we show that the core of the construction can be analysed at an abstract level, yielding a theorem of pure category theory which underlies the previous results. This opens the way to several new examples; in particular we demonstrate an application to Petri nets.     

融合多集群的ECCSSM分布式调度器研究与设计

针对目前的Windows CCS调度系统无法进行多集群间作业调度的情况,设计了一种名为ECCSSM分布式调度系统,使CCS调度系统可以实现跨多个集群的协同分布式调度。通过对已有的Windows CCS的调度系统进行功能上的补充,尤其是分布式协同调度功能的引入,实现了单个集群间以P2P方式调度并行作业,不仅可以合理利用计算资源,而且可以提高整个计算系统的可扩展性。     

A theory of processes with localities

We study a notion of observation for concurrent processes which allows the observer to see the distributed nature of processes, giving explicit names for the location of actions. A general notion of bisimulation related to this observation of distributed systems is introduced. Our main result is that these bisimulation relations, particularized to a process algebra extending CCS, are completely axiomatizable. We discuss in detail two instances of location bisimulations, namely the location equivalence and the location preorder.This work has been partly supported by the ESPRIT/BRA project CEDISYS.     

Parametric channels via label expressions in CCS

CCS, the Calculus of Communicating Systems devised by Milner, has proved extremely successful for providing, via translation, a sound mathematical basis for a wide class of concurrent languages. Nevertheless, as it stands, it suffers from a limitation: it is impossible to determine at run time the channel on which to send or receive a communication. There are various possibilities for giving CCS such ability, but the price can be a drastic change in the language and the theory of CCS.Here we present a simple solution to this problem, which keeps language and theory almost unchanged, at least in fundamental aspects: the essential idea is to extend CCS by allowing (channel-) label expressions. We also show various applications of this extended version of CCS.     

Eventor: an authoring system for interactive multimedia applications

Programming, testing, and maintaining interactive multimedia applications (IMAs) are still difficult and expensive, while substantial progress has been made to reduce the burden on authors. As IMAs get larger and more complex the difficulties will increase. To overcome the complexity of such IMAs, we argue that authoring systems should provide such facilities as (1) a traditional and intuitivedivide-and-conquer paradigm for solving large and complex problems in various fields, (2)formal specification of the behaviors of IMAs for checking the syntactic correctness of visual expressions or semantic anomalies, and (3)automatic aids like validation of temporal constraints and verification of visual expressions. In this paper, we investigate the properties of IMAs for recognizing the inherent interactivity and concurrency. We propose a specification method based on Milner'sCalculus of Communicating Systems (CCS), which is a well-known formal mechanism for specifying the concurrency in various distributed applications. We also design and implement an authoring system calledEventor (Event Editor), which is based on CCS and composed of three tools: a Temporal Synchronizer, a Spatial Synchronizer, and a User Interaction Builder. They focus on describing the temporal and spatial synchronizations and user interactions while they rely on existing tools in Intel's Digital Video Interactive (DVI) for supporting other functionalities. By editing a simple computer aided instruction (CAI) application, we illustrate that our specification mechanism is well-suited for handling the interactivity of multimedia applications, and Eventor is a simple, efficient, and powerful enough tool to handle practical applications. Especially the incremental refinement and the formal specification based on the CCS allow Eventor to be extended with formal verifications to cope with large and complex applications.     

Simulating distributed and coordinated conveying systems

We present the design and implementation of a new object-oriented simulation platform for a decentralized material handling system called the Coordinated Conveying System (CCS). CCS is a new approach to conveying entities, i.e., materials and people. It is also a generalized framework in which the connections between structure and behavior can be systematically studied. In this system, a collection of mobile units moves periodically along fixed tracks. Entities are transferred from some input to an output unit by the mobile units; entities can also transfer between mobile units during a space–time event called a rendezvous. This systems framework and model of conveying exposes a rich spectrum of spatio-temporal behaviors that have interesting connections to core issues in scheduling, resource allocation, communication, embedded systems, automation, and programming. The complexity of CCS arises from the interactions between the mobile units; hence, it is difficult to construct a system-level model for these dynamic behaviors, even though the behavior of individual units is simple. For these reasons, the simulator we present enables a systematic investigation of cyber-physical issues in CCS. Since all the details of CCS are not yet fully understood, we designed an extensible simulator using the Model-View-Controller architecture. The object-oriented approach helped us to model the CCS artifacts in a natural manner and, hence, reduced the complexity of our design.     

A transformation system for concurrent processes

Program transformation techniques have been extensively studied in the framework of functional and logic languages, where they were applied mainly to obtain more efficient and readable programs. All these works are based on the Unfold/Fold program transformation method developed by Burstall and Darlington in the context of their recursive equational language. The use of Unfold/Fold based transformations for concurrent languages is a relevant issue that has not yet received an adequate attention. In this paper we define a transformation methodology for CCS. We give a set of general rules which are a specialization of classical program transformation rules, such as Fold and Unfold. Moreover, we define the general form of other rules, “oriented” to the goal of a transformation strategy, and we give conditions for the correctness of these rules. We prove that a strategy using the general rules and a set of goal oriented rules is sound, i.e. it transforms CCS programs into equivalent ones. We show an example of application of our method. We define a strategy to transform, if possible, a full CCS program into an equivalent program whose semantics is a finite transition system. We show that, by means of our methodology, we are able to a find finite representations for a class of CCS programs which is larger than the ones handled by the other existing methods. Our transformational approach can be seen as unifying in a common framework a set of different techniques of program analysis. A further advantage of our approach is that it is based only on syntactic transformations, thus it does not requires any semantic information. Received: 24 April 1997 / 19 November 1997     

Satisfying constraint sets through convex envelopes

In this article, we present a general representation for constraint satisfaction problems with disjunctive relations called cluster constraint systems (CCS). For this representation, we develop a novel and simple approach for solving CCSs using convex envelopes. These envelopes can be used to decompose the feasible space of the CCS through convex approximations. We explore interval reasoning as a case study of CCS. Our experimental results demonstrate that such CCS can be effectively and efficiently solved through convex enveloping with very modest branching requirements in comparison to other generic as well as specialized algorithms for interval reasoning. In fact, convex enveloping solves significantly more cases and more efficiently than other methods used in our test bed.     

An interpreter for LOTOS,a specification language for distributed systems

LOTOS is an executable specification language for distributed systems currently being standardized within ISO as a tool for the formal specification of open systems interconnection protocols and services. It is based on an extended version of Milner's calculus of communicating systems (CCS) and on ACT ONE abstract data type (ADT) formalism. A brief introduction to LOTOS is given, along with a discussion of LOTOS operational semantics, and of the executability of LOTOS specifications. Further, an account of a prototype LOTOS interpreter is given, which includes an interactive system that allows the user to direct the execution of a specification (for example, for testing purposes). The interpreter was implemented in YACC/LEX, C and Prolog. The following topics are discussed: syntax and static semantics analysis; translation from LOTOS external format to internal representation; evaluation of ADT value expressions and extended CCS behaviour expressions. It is shown that the interpreter can be used in a variety of ways: to recognize whether a given sequence of interactions is allowed by the specification; to generate randomly chosen sequences of interactions; in a user-guided generation mode, etc.     

Two Case Studies of Semantics Execution in Maude: CCS and LOTOS

We explore the features of rewriting logic and, in particular, of the rewriting logic language Maude as a logical and semantic framework for representing and executing inference systems. In order to illustrate the general ideas we consider two substantial case studies. In the first one, we represent both the semantics of Milner’s CCS and a modal logic for describing local capabilities of CCS processes. Although a rewriting logic representation of the CCS semantics is already known, it cannot be directly executed in the default interpreter of Maude. Moreover, it cannot be used to answer questions such as which are the successors of a process after performing an action, which is used to define the semantics of Hennessy-Milner modal logic. Basically, the problems are the existence of new variables in the righthand side of the rewrite rules and the nondeterministic application of the semantic rules, inherent to CCS. We show how these problems can be solved in a general, not CCS dependent way by controlling the rewriting process by means of reflection. This executable specification plus the reflective control of rewriting can be used to analyze CCS processes. The same techniques are also used to implement a symbolic semantics for LOTOS in our second case study. The good properties of Maude as a metalanguage allow us to implement a whole formal tool where LOTOS specifications without restrictions in their data types (given as ACT ONE specifications) can be executed. In summary, we present Maude as an executable semantic framework by providing easy-tool-building techniques for a language given its operational semantics.Research supported by CICYT projects Desarrollo Formal de Sistemas Distribuidos (TIC97-0669-C03-01) and Desarrollo Formal de Sistemas Basados en Agentes Móviles (TIC2000-0701-C02-01).     

State-oriented Noninterference for CCS

We address the question of typing noninterference (NI) in the calculus CCS, in such a way that Milner's translation into CCS of a standard parallel imperative language preserves both an existing NI property and the associated type system. Recently, Focardi, Rossi and Sabelfeld have shown that a variant of Milner's translation, restricted to the sequential fragment of the language, maps a time-sensitive NI property to that of Persistent Bisimulation-based Non Deducibility on Compositions (PBNDC) on CCS. However, since CCS was not equipped with a type system, the question of whether the translation preserves types could not be addressed. We extend Focardi, Rossi and Sabelfeld's result by showing that a slightly simpler variant of Milner's translation preserves a time-insensitive NI property on the full parallel language, by mapping it again to PBNDC. As a by-product, we formalise a folklore result, namely that Milner's translation preserves a behavioural equivalence on programs. We present a simple type system ensuring PBNDC on CCS, inspired by existing type systems for the π-calculus. Unfortunately, this type system as it stands is too restrictive to grant the expected type preservation result. We sketch a solution to overcome this problem.     

Enabling technologies for e-business

While distributed object concepts can be difficult to grasp at first, applying them to build reusable components eventually leads to faster time to market. And now a host of enabling technologies is available, making it easier to use distributed objects for Web based e-business projects. These enabling technologies provide the technical underpinnings for Web-enabled object architectures. Web-enabled object architectures integrate the power of objects with the Web's distribution capabilities. But we need special tools to help minimize the complexities of using distributed object technologies. The advent of application servers and the benefits of distributed object technologies remove the bounds that previously restricted the Web. Companies can use these new technologies to embrace an expanded scope of business that will in turn continue to generate further requirements for new technology     

A fully abstract semantics for value-passing CCS for trees

We propose a fully abstract semantics for valuepassing CCS for trees (VCCTS) with the feature that processes are located at the vertices of a graph whose edges describe possible interaction capabilities. The operational semantics is given both in terms of a reduction semantics and in terms of a labelled transition semantics. We develop a theory of behavioral equivalences by introducing both weak barbed congruence and weak bisimilarity. In particular, we show that, on image-finite processes, weak barbed congruence coincides with weak bisimilarity. To illustrate potential applications and the powerful expressiveness of VCCTS, we formally compare VCCTS with some well-known models, e.g., dynamic pushdown networks, top-down tree automata and value-passing CCS.     

Secure design for cloud control system against distributed denial of service attack

Nowadays, the development of cloud computing has given power to the resource constrained network control system (NCS) to out source heavy computations to the cloud server. However, the development of Cloud Computing produced many security challenges regarding the cyber physical connection between the cloud and control system. The connection between the control system and cloud server can be subjected to distributed denial of service (DDoS) attack by an attacker to destabilize the NCS. In this paper, we will address this issue by building a secure mechanism for such systems. We will design a detection approach and a mitigation approach for better stable performance of NCS. To ensure the stability of NCS at the time of DDoS attack, we will also design a switching mechanism (SM) for cloud control system (CCS) when there are no more real time solutions available from the cloud. Finally, we will apply the proposed mechanism to an unmanned arial vehicle (UAV). Our simulation results show that the mechanism works well in stability and protection of NCS under DDoS attack.     

Specifications of distributed programs

This paper discusses informal specifications of distributed programs, that is, programs that reside at nodes connected by a network. Such programs often have performance requirements, such as high availability and concurrency, that make it difficult to specify their behavior. These requirements often have an effect on the functional behavior of a program, forcing designers to change their initial expectations. In this paper we show how to give user-oriented specifications of the functional behavior of programs with such requirements. We propose a structure for specifications that distinguishes expected and desirable effects from undesirable ones. We believe that this distinction is an important one for both users and implementers of a system, and that it makes the specifications easier to understand. We illustrate our approach by giving example specifications of several distributed programs that have been described in the literature.     

A categorical framework for typing CCS-style process communication

Category theory has proved a useful tool in the study of type systems for sequential programming languages. Various approaches have been proposed to use categorical models to examine the type structures appropriate to concurrent systems. In this paper, we outline some of these approaches, such as interaction categories, and argue that they are not appropriate to model the handshake communication mechanism as used e.g. in CCS or the π-calculus. We propose an alternative general categorical framework for examining the type structure of such systems, and exhibit its categorical structure, which is similar to that of existing approaches. We then examine in detail an instance of this framework, based on a simple fragment of CCS. We prove that it is isomorphic to a syntactic category constructed from a process algebra similar to CCS, with a fusion operator, as in the fusion calculus. Thus, we make explicit some of the type structure implicitly present in such a process algebra.     

Chaotic cuckoo search

This study proposes a novel chaotic cuckoo search (CCS) optimization method by incorporating chaotic theory into cuckoo search (CS) algorithm. In CCS, chaos characteristics are combined with the CS with the intention of further enhancing its performance. Further, the elitism scheme is incorporated into CCS to preserve the best cuckoos. In CCS method, 12 chaotic maps are applied to tune the step size of the cuckoos used in the original CS method. Twenty-seven benchmark functions and an engineering case are utilized to investigate the efficiency of CCS. The results clearly demonstrate that the performance of CCS together with a suitable chaotic map is comparable as well as superior to that of the CS and other metaheuristic algorithms.     

Concurrent counting is harder than queuing

We compare the complexities of two fundamental distributed coordination problems, distributed counting and distributed queuing, in a concurrent setting. In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each participating processor receives the rank of its operation in the total order, where as in queuing, a processor receives the identity of its predecessor in the total order. Many coordination applications can be solved using either distributed counting or queuing, and it is useful to know which of counting or queuing is the easier problem.Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high and low diameter graphs. For all these topologies, we show that the concurrent delay complexity of a particular solution to queuing, the arrow protocol, is asymptotically smaller than a lower bound on the complexity of any solution to counting.     

Representing CCS programs by finite predicate/transition nets

Summary A construction is given which for CCS programs (in which every choice and recursion starts sequentially) yields a finite and strict predicate/ transition net. Consistency of this construction is proved not only with respect to the standard interleaving semantics but with respect to the distributed operational semantics of Degano, De Nicola, and Montanari which additionally models the concurrency explicitly.The work presented here has been carried out at the Institute for Informatics of the Technical University of Munich while the author was supported by an Ernst-von-Siemens scholarship