More Web Proxy on the site http://driver.im/

research-article

Self-Stabilizing Real-Time OPS5 Production Systems

Authors:

Albert Mo Kim Cheng,

Seiya FujiiAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 16, Issue 12

Pages 1543 - 1554

https://doi.org/10.1109/TKDE.2004.95

Published: 01 December 2004 Publication History

Abstract

We examine the task of constructing bounded-time self-stabilizing rule-based systems that take their input from an external environment. Bounded response-time and self-stabilization are essential for rule-based programs that must be highly fault-tolerant and perform in a real-time environment. We present an approach for solving this problem using the OPS5 programming language as it is one of the most expressive and widely used rule-based programming languages. Bounded response-time of the program is ensured by constructing the state space graph so that the programmer can visualize the control flow of the program execution. Potential infinite firing sequences, if any, should be detected and the involved rules should be revised to ensure bounded termination. Both the input variables and internal variables are made fault-tolerant from corruption caused by transient faults via the introduction of new self-stabilizing rules in the program. Finally, the timing analysis of the self-stabilizing OPS5 program is shown in terms of the number of rule firings and the comparisons performed in the Rete network.

References

[1]

Y. Afek and G.M. Brown, “Self-Stabilization of the Alternating-Bit Protocol,” Proc. Eighth Symp. Reliable Distributed Systems, Oct. 1989.]]

[2]

S. Aggarwal and S. Kutten, “Time Optimal Self-Stabilizing Spanning Tree Algorithm,” Proc. 13th Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS '93), pp. 400-410, 1993.]]

Digital Library

[3]

A. Aiken J. Widom and J.M. Hellerstein, “Behavior of Database Production Rules: Termination, Confluence and Observable Determinism,” Proc. Int'l Conf. Management of Data (SIGMOD), 1992.]]

Digital Library

[4]

A. Arora S. Dolev and M.G. Gouda, “Maintaining Digital Clocks in Step,” Parallel Processing Letters, vol. 1, pp. 11-18, 1991.]]

[5]

A. Arora and M.G. Gouda, “Closure and Convergence: A Foundation of Fault-Tolerant Computing,” IEEE Trans. Software Eng., vol. 19, pp. 1015-1027, 1993.]]

Digital Library

[6]

A. Arora and M.G. Gouda, “Distributed Reset,” IEEE Trans. Computers, vol. 43, pp. 1026-1038, 1994.]]

Digital Library

[7]

A. Arora S. Kulkarni and M. Demirbas, “Resettable Vector Clocks,” Proc. 19th Ann. ACM Symp. Principles of Distributed Computing, pp. 269-278, 2000.]]

Digital Library

[8]

A. Arora and M. Nesterenko, “Unifying Stabilization and Termination in Message-Passing Systems,” Proc. the 21st IEEE Int'l Conf. Distributed Computing Systems (ICDCS '01), pp. 99-106, 2001.]]

Digital Library

[9]

B. Awerbuch S. Kutten Y. Mansour B. Patt-Shamir and G. Varghese, “Time Optimal Self-Stabilizing Synchronization,” Proc. 25th Ann. ACM Symp. Theory of Computing (STOC93), pp. 652-661, 1993.]]

Digital Library

[10]

B. Awerbuch and R. Ostrovsky, “Memory-Efficient and Self-Stabilizing Network Reset,” Proc. 13th Ann. ACM Symp. Principles of Distributed Computing (PODC '94), pp. 254-263, 1994.]]

Digital Library

[11]

B. Awerbuch B. Patt-Shamir and G. Varghese, “Bounding the Unbounded (Distributed Computing Protocols),” Proc. IEEE Conf. Computer Comm. (INFOCOM '94), pp. 776-783, 1994.]]

[12]

F. Barachini, “Frontiers in Run-Time Prediction for the Production-System Paradigm,” AI Magazine, vol. 15, no. 3, pp. 47-61, Fall 1994.]]

Digital Library

[13]

E. Baralis S. Ceri and S. Paraboschi, “Compile-Time and Runtime Analysis of Active Behaviors,” IEEE Trans. Software Eng., vol. 10, no. 3, pp. 353-370, May/June 1998.]]

Digital Library

[14]

G.M. Brown M.G. Gouda and C.-L. Wu, “Token Systems that Self-Stabilize,” IEEE Trans. Computers, vol. 38, no. 6, pp. 845-852, June 1989.]]

Digital Library

[15]

L. Brownston R. Farrell E. Kant and N. Martin, Programming Expert Systems in OPS5. Reading, Mass.: Addison-Wesley, 1986.]]

Digital Library

[16]

J.E. Burns and J. Pachl, “Uniform Self-Stabilizing Rings,” ACM Trans. on Programming Languages and Systems, vol. 11, no. 2, pp.nbsp330-344, Apr. 1989.]]

Digital Library

[17]

S. Ceri and J. Widom, “Deriving Production Rules for Constraint Maintenance,” Proc. Int'l Conf. on Very Large Data Bases (VLDB), Aug. 1990.]]

Digital Library

[18]

S. Chandrasekar and P.K. Srimani, “A Self-Stabilizing Algorithm to Synchronize Digital Clocks in a Distributed System,” Computers and Electrical Eng., vol. 20, no. 6, pp. 439-444, 1994.]]

Digital Library

[19]

J. Chen and A.M.K. Cheng, “Predicting the Response Time of OPS5-Style Production Systems,” Proc. 11th IEEE Conf. AI Applications, Feb. 1995.]]

Digital Library

[20]

A.M.K. Cheng, “ Timing Analysis of Self-Stabilizing Programs,” technical report, Dept. of Computer Sciences, Univ. of Texas at Austin, 1988.]]

[21]

A.M.K. Cheng, “Analysis and Synthesis of Real-Time Rule-Based Decision Systems,” PhD dissertation, Dept. of Computer Sciences, Univ. of Texas at Austin, 1990.]]

Digital Library

[22]

A.M.K. Cheng, “Self-Stabilizing Real-Time Rule-Based Systems,” Proc. 11th Symp. Reliable Distributed Systems, pp. 172-179, 1992.]]

[23]

A.M.K. Cheng and J.-R. Chen, “Response Time Analysis of OPS5 Production Systems,” IEEE Trans. Knowledge and Data Eng., vol. 12, no. 3, pp. 391-409, May/June 2000.]]

Digital Library

[24]

A.M.K. Cheng and H. Tsai, “A Graph-Based Approach for Timing Analysis and Refinement of OPS5 Knowledge-Based Systems,” IEEE Trans. Knowledge and Data Eng., vol. 16, no. 2, pp. 271-288, Feb. 2004.]]

Digital Library

[25]

J.-R. Chen and A.M.K. Cheng, “Response Time Analysis of EQL Real-Time Rule-Based Systems,” IEEE Trans. Knowledge and Data Eng., vol. 7, no. 1, pp. 26-43, Feb. 1995.]]

Digital Library

[26]

A.M.K. Cheng J.C. Browne A.K. Mok and R.-H. Wang, “Analysis of Real-Time Rule-Based Systems with Behavioral Constraint Assertions Specified in Estella,” IEEE Trans. Software Eng., vol 19, no. 9, pp. 863-885, Sept. 1993.]]

Digital Library

[27]

A.M.K. Cheng and S. Fujii, “Bounded-Response-Time Self-Stabilizing OPS5 Production Systems,” Proc. 14th Int'l Parallel and Distributed Processing Symp. (IPDPS 2000), pp. 399-404, 2000.]]

Digital Library

[28]

A.M.K. Cheng and C.-K. Wang, “Fast Static Analysis of Real-Time Rule-Based Systems to Verify Their Fixed Point Convergence,” Proc. Fifth IEEE Conf. Computer Assurance, pp. 46-56, June 1990.]]

[29]

G. Ciardo and C. Lindemann, “Comments on `Analysis of Self-Stabilizing Clock Synchronization by Means of Stochastic Petri Nets',” 1995.]]

[30]

A. Ciuffoletti, “Using Simple Diffusion to Synchronize Clocks in a Distributed System,” Proc. IEEE 14th Int'l Conf. Distributed Computing Systems, pp. 484-491, 1994.]]

[31]

A. Ciuffoletti, “Self-Stabilizing Clock Synchronization in a Hierarchical Network,” Proc. Fourth Workshop Self-Stabilizing Systems (published in association with the 19th IEEE Int'l Conf. Distributed Computing Systems (ICDCS '99)), pp. 86-93, 1999.]]

Digital Library

[32]

T. Cooper and N. Wogrin, Rule-Based Programming with OPS5. San Mateo, Calif.: Morgan Kaufmann, 1988.]]

Digital Library

[33]

E.W. Dijkstra, “EWD391 Self-Stabilization in Spite of Distributed Control,” Selected Writings on Computing: A Personal Perspective, pp.nbsp41-46, Berlin: Springer-Verlag, 1992.]]

[34]

E.W. Dijkstra, “Self Stabilizing Systems in Spite of Distributed Control,” Comm. ACM, vol. 17, pp. 643-644, 1974.]]

Digital Library

[35]

S. Dolev, “Optimal Time Self-Stabilization in Uniform Dynamic Systems,” Proc. Sixth IASTED Int'l Conf. Parallel and Distributed Computing and Systems, pp. 25-28, 1994.]]

[36]

S. Dolev A. Israeli and S. Moran, “Self-Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity,” Distributed Computing, vol. 7, pp. 3-16, 1993.]]

Digital Library

[37]

S. Dolev J. L. Welch, “Wait-Free Clock Synchronization,” Proc. 12th Ann. ACM Symp. Principles of Distributed Computing, pp. 97-107, 1993.]]

Digital Library

[38]

S. Dolev and J.L. Welch, “Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults,” Proc. Second Workshop Self-Stabilizing Systems, pp. 9.1-9.12, 1995.]]

[39]

S. Dolev, “Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graphs,” J. Real-Time Systems, vol. 12, no. 1, pp. 95-107, 1997.]]

Digital Library

[40]

S. Dolev and T. Herman, “Superstabilizing Protocols for Dynamic Distributed Systems,” Chicago J. Theoretical Computer Science, vol. 3, no. 4, 1997.]]

[41]

M. Flatebo and A.K. Datta, “Two-State Self-Stabilizing Algorithms for Token Rings,” IEEE Trans. Software Eng., vol. 20, pp. 500-504, 1994.]]

Digital Library

[42]

M. Flatebo A.K. Datta and A.A. Schoone, “Self-Stabilizing Multi-token Rings,” Distributed Computing, vol. 8, pp. 133-142, 1994.]]

Digital Library

[43]

M. Flatebo A.K. Datta and B. Bourgon, “Self-Stabilizing Load Balancing Algorithms,” Proc. IEEE 13th Ann. Int'l Pheonix Conf. Computers and Comm., 1994.]]

[44]

C.L. Forgy, “OPS5 Users Manual,” Technical Report CMU-CS-81-135, Dept. of Computer Science, Carnegie-Mellon Univ., 1981.]]

[45]

C.L. Forgy, “Rete: A Fast Algorithm for Many Pattern/Many Object Pattern Match Problem,” Artificial Intelligence, vol. 19, 1982.]]

[46]

C.L. Forgy, “The OPS Languages: An Historical Overview,” PC AI, Sept. 1995.]]

[47]

S. Ghosh, “Binary Self-Stabilization in Distributed Systems,” Information Processing Letters, vol. 40, pp. 153-159, Nov. 1991.]]

Digital Library

[48]

S. Ghosh, “Agents, Distributed Algorithms, and Stabilization,” Proc. Computing and Combinatorics (COCOON 2000), pp. 242-251, 2000.]]

Digital Library

[49]

J. Giarratano and G. Riley, Expert Systems: Principles and Programming. PWS Pub, 1994.]]

Digital Library

[50]

M.G. Gouda and N Multari, “Stabilizing Communication Protocols,” IEEE Trans. Computers, vol. 40, pp. 448-458, 1991.]]

Digital Library

[51]

A. Gupta, “Parallelism in Production Systems,” PhD thesis, Carnegie-Mellon Univ., 1985.]]

Digital Library

[52]

J.J. Helly, “Distributed Expert System for Space Shuttle Flight Control,” PhD dissertation, Dept. of Computer Science, Univ. of California at Los Angeles, 1984.]]

Digital Library

[53]

T. Herman, “A Comprehensive Bibliography on Self-Stabilization,” Chicago J. Theoretical Computer Science, working paper, 2002.]]

[54]

T. Ishida, “Parallel Rule Firing in Production Systems,” IEEE Trans. Knowledge and Data Eng., vol. 3, no. 1, Mar. 1991.]]

Digital Library

[55]

J.A. Kang and A.M.K. Cheng, “Reducing Matching Time for OPS5 Production Systems,” Proc. COMPSAC, pp. 429-434, 2001.]]

Digital Library

[56]

M.H. Karaata and K.A. Saleh, “A Distributed Self-Stabilizing Algorithm for Finding Maximum Matching,” Computer Systems Science and Eng., vol. 15, no. 3, pp. 175-180, 2000.]]

[57]

M.H. Karaata and F. Al-Anzi, “A Dynamic Self-Stabilizing Algorithm for Finding Strongly Connected Components,” Proc. 18th Ann. ACM Symp. Principles of Distributed Computing (PODC '99), p. 276, 1999.]]

Digital Library

[58]

S. Katz and K. Perry, “Self-Stabilizing Extensions for Message-Passing Systems,” Proc. Ninth Ann. Symp. Principles of Distributed Computing, pp. 91-101, 1990.]]

Digital Library

[59]

P.-Y. Lee and A.M.K. Cheng, “HAL: A Faster Match Algorithm,” IEEE Trans. Knowledge and Data Eng., vol. 14, no. 5, Sept./Oct. 2002.]]

Digital Library

[60]

M. Lin, “Timing Analysis of PL Programs,” Proc. 24th IFAC/IFIP Workshop Real-Time Programming & Third Int'l Workshop Active & Real-Time Database Systems, May-June 1999.]]

[61]

C.A. Marsh, “The ISA Expert System: A Prototype System for Failure Diagnosis on the Space Station,” MITRE Report, The MITRE Corp., Houston, Texas, 1988.]]

Digital Library

[62]

D.P. Miranker, “TREAT: A New and Efficient Algorithm for AI Production Systems,” PhD thesis, Columbia Univ., 1987.]]

Digital Library

[63]

F. Petit and V. Villain, “A Space-Efficient and Self-Stabilizing Depth-First Token Circulation Protocol for Asynchronous Message-Passing Systems,” Proc. Euro-Par '97 Parallel Processing, pp.nbsp476-479, 1997.]]

Digital Library

[64]

G.W. Rosenwald and C.-C. Liu, “Rule-Based System Validation through Automatic Identification of Equivalence Classes,” IEEE Trans. on Knowledge and Data Eng., vol. 9, no. 1, pp. 24-31, Jan./Feb. 1997.]]

Digital Library

[65]

J.G. Schmolze, “Detecting Redundant Production Rules,” Proc. 14th Nat'l Conf. Artificial Intelligence, 1997.]]

Digital Library

[66]

H.-Y. Tsai and A.M.K. Cheng, “Termination Analysis of OPS5 Expert Systems,” Proc. 12th Nat'l Conf. Artificial Intelligence (AAAI), pp. 193-198, Aug. 1994.]]

Digital Library

[67]

R. Washington, “Autonomous Rovers for Mars Exploration,” Proc. IEEE Aerospace Conf., 1999.]]

[68]

R. Washington, “On-Board Real-Time State and Fault Identification for Rovers,” Proc. IEEE Int'l Conf. Robotics and Automation, 2000.]]

[69]

B. Zupan and A.M.K. Cheng, “Optimization of Rule-Based Systems Using State Space Graphs,” IEEE Trans. Knowledge and Data Eng., vol. 10, no. 2, pp. 238-254, Mar./Apr. 1998.]]

Digital Library

Cited By

Qiao YLeng CWang HLiu JSuen CAghdam AGuo MHong JNadimi E(2013)Developing a real-time inference approach for rule-based reasoning systemsProceedings of the 2013 Research in Adaptive and Convergent Systems10.1145/2513228.2513303(22-27)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2513228.2513303
Andrei SChin WCheng ALupu M(2006)Automatic Debugging of Real-Time Systems Based on Incremental Satisfiability CountingIEEE Transactions on Computers10.1109/TC.2006.9755:7(830-842)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1109/TC.2006.97

Index Terms

Self-Stabilizing Real-Time OPS5 Production Systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Triggers and rules
2. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Specialized application languages
  2. Software organization and properties
    1. Software system structures
      1. Software system models
        State systems

Recommendations

Bounded-Response-Time Self-Stabilizing OPS5 Production Systems
IPDPS '00: Proceedings of the 14th International Symposium on Parallel and Distributed Processing

This paper examines the task of constructing bounded-time self-stabilizing rule-based systems that take their input from an external environment. Bounded response-time and self-stabilization are essential for rule-based programs that must be highly ...
Recovery Device for Real-Time Dual-Redundant Computer Systems

This paper proposes the design of specialized hardware, called Recovery Device, for a dual-redundant computer system that operates in real-time. Recovery Device executes all fault-tolerant services including fault detection, fault type determination, ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 16, Issue 12

December 2004

140 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2004.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qiao YLeng CWang HLiu JSuen CAghdam AGuo MHong JNadimi E(2013)Developing a real-time inference approach for rule-based reasoning systemsProceedings of the 2013 Research in Adaptive and Convergent Systems10.1145/2513228.2513303(22-27)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2513228.2513303
Andrei SChin WCheng ALupu M(2006)Automatic Debugging of Real-Time Systems Based on Incremental Satisfiability CountingIEEE Transactions on Computers10.1109/TC.2006.9755:7(830-842)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1109/TC.2006.97

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents