Response time analysis of OPS5 production systems

The paper focuses on the problem of determining a priori the maximal response time of rule based programs. The response time analysis problem is an important problem, especially for real time systems. We study this problem in the context of OPS5 production systems. Two aspects of the response time of a program are investigated, the maximal number of rule firings and the maximal number of basic comparisons made by the Rete network during the execution of the program. The response time analysis problem is in general undecidable. However, a program terminates in a finite time if the rule triggering pattern of this program satisfies certain conditions. We present four such termination conditions for OPS5 production systems. An algorithm for computing an upper bound on the number of rule firings is then given. To have a better idea of the time required during execution, we present an algorithm that computes the maximal time required during the match phase in terms of the number of comparisons made by the Rete network. This measurement is sufficient since the match phase consumes about 90 percent of the execution time     

Shortening matching time in OPS5 production systems

A rule-based system must satisfy stringent timing constraints when applied to a real-time environment. As the scale of rule-based expert systems increases, the efficiency of systems becomes a pressing concern. The most critical performance factor in the implementation of a production system is the condition-testing algorithm. We propose a new method based on the widely used RETE match algorithm. We show an approach designed to reduce the response time of rule-based expert systems by reducing the matching time. There are two steps in the method we propose: The first makes an index structure of the tokens to reduce the /spl alpha/-node-level join candidates. The second chooses the highest time tag for certain /spl beta/-nodes to reduce the amount of combinatorial match that is problematical in a real-time production system application. For this purpose, a simple compiler is implemented in C and the response time of test programs is measured.     

Execution of OPS5 production systems on a massively parallel machine

In recent years, the development of expert systems implemented by rule-based production systems has emerged as one of the dominant paradigms in the field of artificial intelligence. While production systems offer important advantages in large-scale AI applications, their use in such applications is typically very costly in execution time. In this paper, we describe an algorithm for executing production systems expressed in the OPS5 language on a massively parallel multiple-SIMD machine called NON-VON, portions of which are currently under construction at Columbia University. The algorithm, a parallel adaptation of Forgy's Rete Match, has been implemented and tested on an instruction-level simulator. We present a detailed performance analysis, based on the implemented code, for the averaged characteristics of six production systems having an average of 910 inference rules each. The analysis predicts an execution rate of more than 850 production firings per second using hardware comparable in cost to a VAX 11/780. By way of comparison, a LISP-based OPS5 interpreter running on a VAX 11/780 typically fires 1 to 5 rules per second, while a Bliss-based interpreter executes 5 to 12 rules per second.     

Self-stabilizing extensions for meassage-passing systems

Summary A self-stabilizing program eventually resumes normal behavior even if excution begins in, an abnormal initial state. In this paper, we explore the possibility of extending an arbitrary program into a self-stabilizing one. Our contributions are: (1) a formal definition of the concept of one program being aself-stabilizing extension of another; (2) a characterization of what properties may hold in such extensions; (3) a demonstration of the possibility of mechanically creating such extensions. The computtional model used is that of an asynchronous distributed message-passing system whose communication topology is an arbitrary graph. We contrast the difficulties of self-stabilization in thismodel with those of themore common shared-memory models. Shmuel Katz received his B.A. in Mathematics and Englisch Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rechovot, Israel. From 1976 to 1981 he was a research at the IBM Israel Scientific Center. Presently, he is an Associate Professor in the Computer Science Department at the Technion in Haifa, Israel. In 1977–78 he visited for a year at the University of California, Berkeley, and in 1984–85 was at the University of Texas at Austin. He has been a consultant and vistor at the MCC Software Technology Program, and in 1988–89 was a visiting scientist at the IBM Watson Research Center. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structure, and programming languages. Kenneth J. Pery has performed research in the area of distributed computing since obtaining Masters and Doctorate degrees in Computer Science from Cornell Univesity. His current interest is in studying problems of a partical nature in a formal context. He was graduated from Princeton University in 1979 with a B.S.E. degree in Electrical Engineering and Computer Science.The Research of this author was partially supported by Research Grant 120-749 and the Argentinian Research Fund at the Technion     

Towards the formal specification of an OPS5 production system architecture

The article presents a formal specification for many important aspects of the OPS5 production systems framework. the article illustrates how an abstract formal specification of a production system can be created and the benefits this provides to those involved in the development of knowledge-based systems. the formal specification is preceded by an informal specification of a production system upon which the formal model is based and the development is illustrated through the use of concrete examples. the notation used is that of “Z” (J. M. Spivey, The Z Notation, Prentice-Hall, Englewood Cliffs, NJ, 1990), a language based upon typed set theory. This language has been used to success in the specification of critical conventional software systems (I. Hayes, Technical Monograph PRG-46, Oxford University Computing Laboratory, Oxford, England, 1985) and which is formal enough to allow for the creation of rigorous specifications, yet is of a form that makes these specifications “readable.” the aim of the article is to show that formal techniques can be applied to areas of knowledge-based system development, thus promoting correctness, reliability, and understanding. © 1994 John Wiley & Sons, Inc.     

A graph-based approach for timing analysis and refinement of OPS5 knowledge-based systems

We examine the problem of predicting the timing behavior of knowledge-based systems for real-time applications. In particular, we describe a suite of tools which analyze OPS5 programs to understand their timing properties. First, a graphical representation of an OPS5 program is defined and evaluated. This graph represents the logical control flows of an OPS5 program. Most of our analysis is based on this data structure. Second, we describe a novel tool which verifies that an OPS5 program can terminate in finite time. If the termination of the OPS5 program is not expected, the "culprit" conditions are detected. These conditions are then used to correct the problem by adding extra rules to the original program. Third, another tool is introduced to aid timing analysis of OPS5 programs. This tool generates a set of test data which maximize the program execution time. Other functions are also provided to facilitate the timing analysis.     

Self-stabilizing somersaults

We investigate the open-loop stability of a planar biped robot performing a periodic motion of forward somersaults with alternating single-leg contacts. The robot has a trunk and two actuated telescopic legs with point feet which are coupled to the trunk by actuated hinges. There is compliance and damping in the hip and in the legs. The concept of open-loop control implies that all actuators of the system receive predetermined inputs that are never altered by any feedback interference. Only with the right choice of model parameters and actuator inputs is it possible to create such self-stabilizing motions exploiting the natural stability properties of the system. These unknowns have been determined using special-purpose stability-optimization methods. The resulting motion is not only stable, but also a more efficient form of forward motion than running for the investigated robot.     

Self-stabilizing multi-token rings

Summary A distributed system consists of a set of loosely connected machines that do not share a global memory. The system isself-stabilizing if it can be started in any global state and achieves consistency all by itself. This also means that the system can deal withinfrequent errors. This paper presents self-stabilizing multi-token rings. A multitoken ring is a generalization of a (one-)token ring. The algorithms presented are generalizations of a self-stabilizing mutual exclusion algorithm by Dijkstra [5] which can also be viewed as a token ring. We develop the algorithms in a stepwise manner, to show how and why we arrived at the final multi-token rings. The final parameterized algorithm represents a set of algorithms, one for each choice of the parameter. This enables one to select the algorithm with an optimal trade-off in desired flexibility versus memory requirements and stabilization time. Mitchell Flatebo received the B.S. degree in Mathematics (1990), the B.S. degree in Computer Science (1990), the M.S. degree in Mathematics (1992), and the M.S. degree in Computer Science (1993) from the University of Nevada, Las Vegas. He is currently a software engineer for Loral Space and Range Systems. His research interests include distributed systems, fault-tolerant computing, and self-stabilization. Ajoy Kumar Datta received the Ph.D. degree in Computer Science from the Jadavpur University, Calcutta, India in 1983. He is currently an Associate Professor of Computer Science at the University of Nevada, Las Vegas. His area of research is distributed and fault-tolerant computing —algorithms and self-stabilization. Anneke Schoone received an M.Sc. degree in Biology in 1978, an M.Sc. degree in Mathematics in 1981, and a Ph.D. degree in Computer Science in 1991 from Utrecht University (The Netherlands). Currently she is a senior research associate at the Department of Computer Science of Utrecht University, supported by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity) of the EC. Her research interests include assertional verification of distributed algorithms and the concept of self-stabilization.The research of this author was supported partially by the ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity), and partially by the Netherlands Organization for Scientific Research (NWO) under contract NF 62-376 (NFI project ALADDIN:Algorithmic Aspects of Parallel and Distributed Systems)     

Self-stabilizing tree ranking

Given a graph G and some property ? (g), a ?-ranking (ordering) of the nodes of G can be defined as a one-to-one function from V to {1, 2, 3, …, n} such that property ?(G) holds for each node i∈V. In this paper we present an O(n ²) self-stabilizing algorithm which, when given a rooted tree T, will provide ?-rankings consistent with the following standard graph traversal properties: (i) preorder traversal; (ii) postorder traversal; (iii) reverse-postorder traversal; (iv) breadth-first traversal; (v) breadth–depth traversal.     

Self-stabilizing distributed queuing

Distributed queuing is a fundamental coordination problem arising in a variety of applications, including distributed shared memory, distributed directories, and totally ordered multicast. A distributed queue can be used to order events, user operations, or messages in a distributed system. This paper presents a new self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the arrow distributed queuing protocol, a simple path-reversal protocol that runs on a spanning tree of the network. We present a proof that the protocol stabilizes to a stable state irrespective of the (perhaps faulty) initial state, and also present an analysis of the time until convergence. The self-stabilizing queuing protocol is structured as a layer that runs on top of any self-stabilizing spanning tree protocol. This additional queuing layer is guaranteed to stabilize in time bounded by a constant number of message delays across an edge, thus establishing that the stabilization time for distributed queuing is not much more than the stabilization time for spanning tree maintenance. The key idea in our protocol is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree.     

基于HTML5的生产装置实时监测可视化

提出一种基于HTML5的生产装置实时监测Web可视化方法。采用基于事件的自触发机制和WebSocket通信协议使服务器端主动传输数据,利用Canvas技术实现无浏览器插件式的页面动态可视化显示。基于ASP?NET平台开发生产装置实时监测Web可视化系统,给出系统架构和实现方法。实际应用结果表明,提出的服务器端自触发机制和WebSocket通信协议有效降低了服务器运行压力和网络吞吐量,提高了系统通信效率;开发的生产装置实时监测Web可视化系统无需安装浏览器插件,数据可视化效果良好。     

Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems

The role of argumentation in supporting various forms of interaction among possibly conflicting autonomous agents has been explicitly recognized in the literature. In argumentation, conflict management is carried out by the formal process of defeat status computation. In this paper we consider the generalization of this process to a distributed setting. We show that significant stabilization problems may arise even in relatively simple cases. A fundamental negative result is then proved: no general self-stabilizing algorithm exists for distributed defeat status computation, indicating that self-stabilizing algorithms for this problem can be defined only under specific conditions. Accordingly, we focus on two cases: an algorithm tailored to a specific family of inference graphs, that include only rebutting defeaters, and an algorithm that applies to any inference graph, also including undercutting defeaters, but may provide (cautiously) incorrect results for some nodes. For both algorithms the worst-case round complexity is analyzed and it is proved that no algorithms with lower complexity exist for the same tasks.     

AN OPS5 IMPLEMENTATION OF QUALITATIVE REASONING ABOUT PHYSICAL SYSTEMS

This paper describes the implementation of WQMS, a general-purpose qualitative modeling environment that integrates the process-centered approach and the constraint-centered approach. A new simulation algorithm is presented in which, owing to this integration, some drawbacks of QSIM are overcome using a depth-first strategy in the assessment of the qualitative states and a reduced set of input variables. With this algorithm it is possible to achieve qualitative simulations in cases in which simulations by QSIM are not feasible, because in some complex systems it is possible neither to specify the initial conditions for all required variables nor to handle the amount of branching that arises with normal computer facilities. An implementation of modeling and simulation of two biological systems is shown; to the best of the authors' knowledge, WQMS is the only environment with which a qualitative simulation can be achieved for these systems.     

Self-stabilizing byzantine asynchronous unison

We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two.     

Self-stabilizing strong fairness under weak fairness

Fairness assumptions have a great impact on distributed algorithms. They play a major role in determining the time complexity and the correctness of algorithms, since progress or freedom from various types of starvation may not be guaranteed without fairness assumptions. In this paper, we present a stabilizing deterministic algorithm allowing simultaneous execution of actions for strong fairness under weak fairness assumption, in addition, we show that the proposed algorithm yields a high degree of concurrency. We conclude the paper with some remarks on issues such as time optimal implementation of strong fairness and open problems related to fairness     

Self-stabilizing group communication in directed networks

This paper presents the first self-stabilizing group membership service, multicast service, and resource allocation service for directed networks. The first group communication algorithm is based on a token circulation over a virtual ring. The second algorithm is based on construction of distributed spanning trees. In addition, a technique is presented that emulates, in a self-stabilizing fashion, any undirected communication network over strongly connected directed networks, is presented. A resource allocation asynchronous algorithm for strongly connected directed networks is presented.Received: 23 July 2003, Published online: 29 June 2004Partially supported by NSF Award CCR-0098305, IBM faculty award, STRIMM consortium, and Israel ministry of defense.     

Discrete event-driven model predictive control for real-time work-in-process optimization in serial production systems

Advanced technologies (e.g., distributed sensors, RFID, and auto-identification) can gather processing information (e.g., system status, uncertain machine breakdown, and uncertain job demand) accurately and in real-time. By combining this transparent, detailed, and real-time production information with production system physical properties, an intelligent event-driven feedback control can be designed to reschedule the release plan of jobs in real-time without work-in-process (WIP) explosion. This controller should obtain the operational benefits of pull (e.g., Toyota’s Kanban system) and still develop a coherent planning structure (e.g., MRPII). This paper focuses on this purpose by constructing a discrete event-driven model predictive control (e-MPC) for real-time WIP (r-WIP) optimization. The discrete e-MPC addresses three key modelling problems of serial production systems: (1) establish a max-plus linear model to describe dynamic transition behaviors of serial production systems, (2) formulate a model-based event-driven production loss identification method to provide feedback signals for r-WIP optimization, and (3) design a discrete e-MPC to generate the optimal job release plan. Based on a case from an industrial sewing machine production plant, the advantages of the discrete e-MPC are compared with the other two r-WIP control strategies: Kanban and MRPII. The results show that the discrete e-MPC can rapidly and cost-effectively reconfigure production logic. It can decrease the r-WIP without deteriorating system throughput. The proposed e-MPC utilizes the available transparent sensor data to facilitate real-time production decisions. The effort is a step forward in smart manufacturing to achieve improved system responsiveness and efficiency.     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

Monitoring distributed real-time systems

This paper emphasizes the power ofmonitoring of distributed real-time systems as a promising tool for both scientific work and practical purposes. Starting out from a number of well-known problems with today's (industrial) real-time systems, a classification of remedial monitoring applications is given. The most important features of a monitoring system suitable for such purposes are discussed and related to the current research into monitoring of (general) distributed systems. Finally, some of the resulting conceptual issues underlying our prototype VTA monitoring system—currently being under development at our department—are presented.     

Analyzing partially-implemented real-time systems

Most analysis methods for real-time systems assume that all the components of the system are at roughly the same stage of development and can be expressed in a single notation, such as a specification or programming language. There are, however, many situations in which developers would benefit from tools that could analyze partially-implemented systems: those for which some components are given only as high-level specifications while others are fully implemented in a programming language. In this paper, we propose a method for analyzing such partially-implemented real-time systems. We consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and graphical interval logic (GIL), a real-time temporal logic. We show how to construct models of the partially-implemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs. The approach can be fully automated, and we illustrate it by analyzing a small example