Real-Time Systems References - Prof. Albert M. K. Cheng

Books (Algorithms, Data Structures, Logic, Theoro of Computation)

A. V. Aho, J. E. Hopcroft and J. D. Ullman,
``The Design and Analysis of Computer Algorithms,''
Addison-Wesley.

Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson, and Clifford Stein,
``Introduction to Algorithms,''
McGraw-Hill College.

C.-L. Chang and R. Lee,
``Symbolic Logic and Mechanical Theorem Proving,''
Academic Press.

M. R. Garey and D. S. Johnson,
``Computers and Intractability: A Guide to the Theory of NP-Completeness,''
Freeman & Co.


Proceedings and Earlier Papers in Real-Time Systems
 
J. Stankovic and K. Ramamritham,
``Advances in Real-Time Systems,''
IEEE-CS Press.

Proceedings of the Annual IEEE-CS Real-Time Systems Symposium.

Proceedings of the Annual IEEE-CS Real-Time Technology and Application
Symposium.

Proceedings of the Annual IEEE-CS Real-Time Operating Systems and Languages
Workshop.

Journal of Real-Time Systems

IEEE Transactions on Computers, Transactions on Software Engineering
.SH
Computer Communication and Networks

B. Chen et al,
``Optimal Synchronous Capacity Allocation for Hard Real-Time Communication
with the Timed Token Protocol,''
\fIProc. 13\uth\d Real-Time Systems Symposium\fR,
Dec. 1992.

X. Huang and A. M. K. Cheng,
``Applying Imprecise Computation Algorithms to
Real-Time Image and Video Transmission,''
\fIProc. IEEE-CS Real-Time Technology and Applications Symp.\fR,
Chicago, IL,
pp. 96-101,
May 1995.

S. Kamat,
``Performance Evaluation of a Bandwidth Allocation Scheme for Guaranteering
Synchronous Messages with Arbitrary Deadlines in an FDDI Network,
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
Dec. 1993.

D. D. Kandlur et al,
``Real-Time Communication in Multihop Networks,''
\fIIEEE Trans. Parallel and Distributed Systems\fR,
Vol. 5, No. 10, Oct. 1994, pp. 1044-1056.

S. Mukherjee et al,
``A Bandwidth Allocation Scheme for Time Constrained Message Transmission
on a Slotted Ring LAN,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
Dec. 1993.

L. N. Nguyen and A. M. K. Cheng,
``An Imprecise Real-Time Image Magnification Algorithm,''
\fIProc. Intl. Symp. on Multimedia Systems\fR,
Yokohama, Japan, Mar. 1996.

L. Sha,
``Scheduling Real-Time Communication on Dual-Link Networks,''
\fIProc. 13\uth\d Real-Time Systems Symposium\fR,
Dec. 1992.
.SH
Distributed and Parallel Systems

J.-R. Chen and A. M. K. Cheng,
``A Fast, Partially Parallelizable
Algorithm for predicting Execution Time of
EQL Rule-Based Programs,''
\fIProc. 23rd Intl. Conf. on Parallel Processing\fR,
St. Charles, IL, Aug. 1994.

A. M. K. Cheng,
``Parallel Execution of Real-Time Rule-Based Systems,''
\fIProc. 7th IEEE-CS Intl. Parallel Processing Symp.\fR,
Newport Beach, California, Apr. 1993.

C.-C. Han and K.-J. Lin,
``Scheduling Parallelizable Jobs on Multiprocessors,''
\fI10\uth\d Real-Time Systems Symp.\fR,
1989.

C. M. Krishna, K. G. Shin, and I. S. Bhandari,
``Processor Trade-offs in Distributed Real-Time Systems,''
\fIIEEE Trans. Computers\fR,
Vol. C-36, No. 9, Sept. 1987, pp. 1030-1040.

K. G. Shin,
``HARTS: A Distributed Real-Time Architecture,''
\fIIEEE Computer\fR,
Vol. 24, May 1991.

K. G. Shin and Y.-C. Chang,
``Load Sharing in Distributed Real-Time Systems with State-Change
Broadcasts,''
\fIIEEE Trans. Computers\fR,
Vol. C-38, Aug. 1989, pp. 1124-1142.

I. Suzuki and T. Kasami,
``A Distributed Mutual Exclusion Algorithm,''
\fIACM Trans. Computer Systems\fR,
Vol. 3, No. 4, Nov. 1985, pp. 344-349.

C.-Y. Wang and A. M. K. Cheng,
``Increasing Production System
Parallelism via Synchronization Minimization and
Look-Ahead Conflict Resolution,''
\fIProc. 24th Intl. Conf. on Parallel Processing\fR,
Oconomowoc, WI,
Vol. III,
pp. 85-92,
Aug. 1995.

S. S. Yau, C. C. Yang, and S. M. Shatz,
``An Approach to Distributed Computing System Software Design,''
\fIIEEE Transactions on Software Engineering\fP\^,
Vol. SE-7, No. 4, July 1981.
.SH
Expert Systems

F. Barachini,
``Frontiers in Run-Time Prediction for the Production-System Paradigm,''
\fIAI Magazine,\fP
Vol. 15, No. 3, pp. 47-61, Fall 1994.

A. M. K. Cheng and C.-H. Chen,
``Efficient Response Time Bound Analysis
of Real-Time Rule-Based Systems,''
\fIProceedings of
7\uth\d Annual IEEE Conference on Computer Assurance (COMPASS '92)\fR,
National Institute of Standards and Technology,
Gaithersburg, Maryland,
June 1992.

J. C. Browne, A. M. K. Cheng, and A. K. Mok,
``Computer-Aided Design of Real-Time Rule-Based Decision Systems,''
to appear in
\fIIEEE Transactions on Software Engineering\fP\^.

J.-R. Chen and A. M. K. Cheng,
``Predicting the Response Time of Real-Time
Rule-Based Programs with Variable-Expression Assignments,''
\fIProc. 6th IEEE-CS Intl. Conf. on
Tools with Artificial Intelligence\fR,
New Orleans, LA,
Nov. 1994.

J.-R. Chen and A. M. K. Cheng,
``Predicting the Response Time of OPS5-style Production Systems,''
\fIProc. IEEE-CS Conf. on Artificial Intelligence
for Applications\fR, Los Angeles, CA, pp. 203-209, Feb. 1995.

A. M. K. Cheng,
``Implementing a Tool for Timing Analysis of
Real-Time Production Systems,''
\fIProceedings of
3rd IEEE International Conference on Tools for Artificial Intelligence\fR,
San Jose, California, November 1991.

A. M. K. Cheng, J. C. Browne, A. K. Mok and R.-H. Wang,
``Estella: A Language for Specifying Behavioral Constraint
Assertions in Real-Time Rule-Based Systems,''
\fIProceedings of
6\uth\d Annual IEEE Conference on Computer Assurance\fR,
National Institute of Standards and Technology,
Gaithersburg, Maryland,
June 1991.

A. M. K. Cheng and C.-K. Wang,
``Fast Static Analysis of Real-Time Rule-Based Systems to
Verify Their Fixed Point Convergence,''
\fIProceedings of the 5\uth\d Annual IEEE Conference on
Computer Assurance\fR,
National Institute of Standards and Technology,
Gaithersburg, Maryland,
June 1990.

T. J. Laffey, P. A. Cox, J. L. Schmidt, S. M. Kao, and J. Y. Read,
``Real-Time Knowledge-Based Systems,''
\fIAI Magazine,\fP
Vol. 9, No. 1, Spring 1988, pp. 27-45.

H.-Y. Tsai and A. M. K. Cheng,
``Termination Analysis of OPS5 Expert Systems,''
\fIProc. 12th National Conf. on Artificial Intelligence (AAAI)\fR,
Seattle, WA, pp. 193-198, Aug. 1994.

C.-K. Wang, A. K. Mok, and A. M. K. Cheng,
``MRL: A Real-Time Rule-Based Production System,''
\fIProc. 11\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Orlando, Florida,
1990.

B. Zupan and A. M. K. Cheng,
``Optimization of Rule-Based Systems via
State Transition System Construction,''
\fIProc. IEEE-CS Conf. on Artificial Intelligence
for Applications\fR, San Antonio, TX, pp. 320-326, March 1994.

B. Zupan and A. M. K. Cheng,
``Response Time Optimization of Rule-Based Expert Systems,''
\fIProc.
SPIE OE/Aerospace Sensing Conference
on
Knowledge-Based Artificial Intelligence Systems in Aerospace and Industry\fR,
Orlando, FL,
1994.
.SH
Fault-Tolerance and Error Recovery

A. M. K. Cheng,
``Self-Stabilizing Real-Time Rule-Based Systems,''
\fIProceedings of
11\uth\d IEEE Symposium on Reliable Distributed Systems\fR,
Houston, Texas,
October 1992.

A. M. K. Cheng,
``On the Implementation of Distributed Agreement Protocols in Computer
Networks,''
\fIProc. IEEE Singapore International Conf. on Networks\fR,
July 1989.

S. Ramos-Thuel and J. K. Strosnider,
``The Transient Server Approach to Scheduling Time-Critical Recovery
Operations,''
\fIProc. 12\uth\d Real-Time Systems Symposium\fR,
San Antonio, TX,
Dec. 1991.

B. Randell,
``System Structure for Software Fault Tolerance,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-1, No. 2, June 1975, pp. 220-232.

S. Rangarajan and S. K. Tripathi,
``Efficient Synchronization of Clocks in a Distributed System,''
\fI12\uth\d IEEE-CS Real-Time Systems Symp.\fR,
1991.

D. L. Russell,
``State Restoration in Systems of Communicating Processes,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-6, No. 2, March 1980, pp. 183-194.

L. Sha, J. Lehoczky, and E. D. Jensen,
``Modular Concurrency Control and Failure Recovery,''
\fIIEEE Trans. Computers\fR,
Vol. 37, No. 2, Feb. 1988, pp. 146-159.
.SH
Formal Specification, Analysis, and Verification

A. Bestavros,
``Specification and Verification of
Real-Time Embedded Systems Using Time-Constrained Reactive Automata,''
\fIProc. 12\uth\d Real-Time Systems Symposium\fR,
San Antonio, TX,
pp. 244-253,
Dec. 1991.

G. Bruno et al,
``A New Petri Net Based Formalism for Specification,
Design and Analysis of Real-Time Systems,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
pp. 294-301,
Dec. 1993.

A. M. K. Cheng,
``Fast Static Timing Analysis of Real-Time Systems,''
\fI25th Hawaii International Conference on System Sciences (HICSS-25)\fR.

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,''
\fIIEEE Transactions on Software Engineering\fR,
Sept. 1993.

A. M. K. Cheng,
``A New Complexity Metric for OPS5 Rule-Based Systems,''
\fIIEEE-CS Intl. Conf. on
Software Engineering and Knowledge
Engineering\fR, San Francisco, California, June 1993.

A. M. K. Cheng,
``Measuring the Structural Complexity of OPS5 Rule-Based Programs,''
to appear in \fIProc. 20th
IEEE-CS Computer Software and Applications (COMPSAC) Conf.\fR,
Seoul, Korea, Aug. 1996.

E. M. Clarke, E. A. Emerson, and A. P. Sistla,
``Automatic Verification of Finite-State Concurrent Systems Using
Temporal Logic Specifications,''
\fIACM Transactions on Programming Languages and Systems,\fP
Vol. 8, No. 2, April 1986, pp. 244-263.

P. Clements et al,
``MT: A Toolset for Specifying and Analyzing Real-Time Systems,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
pp. 12-22,
Dec. 1993.

K. L. Heninger,
``Specifying Software Requirements for Complex Systems:
New Techniques and their Applications,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-6, No. 1, Jan. 1980, pp. 2-13.

F. Jahanian, R. Lee, and A. K. Mok,
``Semantics of Modechart in Real Time Logic,''
\fIProc. 21st Hawaii International Conf. Systems Science\fR,
Jan. 1988.

F. Jahanian and A. K. Mok,
``Safety Analysis of Timing Properties in Real-Time Systems,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-12, No. 9, Sept. 1986, pp. 890-904.

S.-S. Lim et al,
``An Accurate Worst Case Timing Analysis for RISC Processors,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-21, No. 7, July 1995, pp. 593-604.

J. Ostroff and W. Wonham,
``Modeling, Specifying, and Verifying
Real-Time Embedded Computing Systems,''
\fIProc. 8\uth\d Real-Time Systems Symposium\fR,
pp. 124-132,
Dec. 1987.

R. E. Shostak,
``On the SUP-INF Method for Proving Presburger Formulas,''
\fIJ. ACM\fR,
Vol. 24, No. 4, Oct. 1977, pp. 529-543.

D. A. Stuart,
``Implementing a Verifier for Real-Time Systems,''
\fIProc. 11\uth\d Real-Time Systems Symp.\fR,
Dec. 1990.
.SH
Operating Systems and Database Systems

Special Section on Temporal and Real-Time Databases,
\fIIEEE Trans. Knowledge and Data Engineering\fR,
Vol. 7, No. 4, Aug. 1995.

R. Abbott and H. Garcia-Molina,
``Scheduling I/O Requests with Deadlines: A Performance Evaluation,''
\fIProc. 11th Real-Time Systems Symposium\fR,
Orlando, Florida,
Dec. 1990.

A. Bestavros and S. Braoudakis,
``Timeliness via Speculation for Real-Time Databases,''
\fIProc. 15\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1994.

A. M. K. Cheng,
``Scheduling Transactions in Real-Time Database Systems,''
\fIProc. IEEE COMPCON\fR, San Francisco, California, Feb. 1993.

A. M. K. Cheng and X. Gu,
``Improving the I/O Performance of Real-Time Database Systems with
Multiple-Disk Storage Structures''
\fIProc. 25th
Intl. Conf. on Parallel Processing\fR,
Bloomingdale, IL,
Vol. I,
pp. 204-211,
Aug. 1996.

A. M. K. Cheng
and L. Zhang,
``An Efficient On-Line Scheduler for
Real-Time Main Memory Database
Systems,''
\fIProc. IEEE Intl. Conf. on Data and Knowledge Systems
for Manufacturing and Engineering\fR,
pp. 680-685,
May 1994.

T. Craig,
``Queueing Spin Lock Algorithms to Support Timing Predictability,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
Dec. 1993.

S. Davidson et al,
``Deadlock Prevention in Concurrent Real-Time Systems,''
J. Real-Time Systems,
Oct. 1993.

B. Gallmeister and C. Lanier,
``Early Experience with POSIX 1003.4 and POSIX 1003.4A,''
\fIProc. 12\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1991.

J. Haritsa, M. Livny, and M. Carey,
``Earliest Deadline Scheduling for Real-Time Database Systems,''
\fIProc. 12\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1991.

C. A. R. Hoare,
``Monitors: an Operating System Structuring Concept,''
\fICACM\fR,
Vol. 17, No. 10, Oct. 1974, pp. 549-557.

W. Kim and J. Srivastava,
Enhancing Real-Time DBMS Performance with
``Multiversion Data and Priority Based Disk Scheduling,''
Proc. 12th Real-Time Systems Symp.,
San Antonio, Texas,
Dec. 1991.

Y. Lin and S. H. Son,
``Concurrency Control in Real-Time Databases by Dynamic Adjustment of
Serialization Order,''
Proc. 11th Real-Time Systems Symp.,
Orlando, Florida,
Dec. 1990.

T. Nakajima,
''Integrated Management of Priority Inversion in
Real-Time Mach,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
Dec. 1993.

K. Schwan et al.,
``CHAOS: Kernel Support for Objects in the Real-Time Domain,''
\fIIEEE Trans. Computers\fR,
Aug. 1987.

K. Schwan et al.,
``High Performance Operating System Primitives for Robotics and
Real-Time Control Systems,''
\fIACM Trans. Computer Systems\fR,
Vol. 5, No. 3, Aug. 1987, pp. 189-231.

J. Stankovic and K. Ramamritham,
``The Design of the Spring Kernel,''
\fIProc. 8\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1987, pp. 146-155.
.SH
Programming Languages

T. P. Baker and O. Pazy,
``Real-Time Features for Ada 9x,''
\fI12\uth\d IEEE-CS Real-Time Systems Symp.\fR,
1991.

E. W. Giering III and T. P. Baker,
``Toward the Deterministic Scheduling of Ada Tasks,''
\fI10\uth\d IEEE-CS Real-Time Systems Symp.\fR,
1989.

Luqi, V. Berzins, and R. Yeh,
``A Prototyping Language for real-Time Software,''
\fIIEEE Trans. Software Engineering\fR,
Vol. 14, Np. 10, Oct. 1988, pp. 1409-1423.

T. W. Mao and R. T. Yeh,
``Communication Port: A Language Concept for Concurrent Programming,''
\fIIEEE Trans. Software Engineering\fR,
Vol. 6, No. 2, March 1980, pp. 194-204.

A. K. Mok,
``The Design of Real-Time Programming Systems Based on Process Models,''
\fIProc. 5\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1984.

E. S. Roberts et al.,
``Task Management in Ada -- a Critical Evaluation for Real-Time
Multiprocessor,''
\fISoftware Practice & Experience\fR,
Vol. 11, No. 10, Oct. 1981, pp. 1019-1052.

A. C. Shaw,
``Reasoning about Time in Higher-Level Language Software,''
\fIIEEE Trans. Software Engineering\fR,
Vol. 15, July 1989, pp. 875-889.

N. Wirth,
``Toward a Discipline of Real-Time Programming,''
\fICACM\fR, Vol. 20, No. 8, Aug. 1977, pp. 577-583.
.SH
Scheduling

M. L. Dertouzos and A. K. Mok,
``Multiprocessor On-line Scheduling of Hard-real-time Tasks,''
\fIIEEE Trans. Software Engineering\fR,
Vol. 15, Dec. 1989, pp. 1497-1506.

S. K. Dhall and C. L. Liu,
``On a Real-Time Scheduling Problem,''
\fIOperations Research\fR,
Vol. 26, No. 1, Feb. 1978, pp. 127-140.

M. R. Garey and D. S. Johnson,
``Two-Processor Scheduling with Start-Times and Deadlines,''
\fISIAM J. Computing\fR,
Vol. 6, 1977, pp. 416-426.

M. R. Garey, D. S. Johnson, B. Simmons, and R. Tarjan,
``Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines,''
\fISIAM J. Computing\fR,
Vol. 10, No. 2, May 1981, pp. 256-269.

R. Gupta and M. Spezialetti,
``Busy-Idle Profiles and Compact Task Graphs:
Compile-time Support for Interleaved and Overlapped Scheduling
of Real-Time Tasks,''
\fIProc. 15\uth\d Real-Time Systems Symposium\fR,
Dec. 1994.

K. Jeffay, D. Stanat, and C. Martel,
``On Non-Preemptive Scheduling of Periodic and Sporadic Tasks,''
\fIProc. 12\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1991.

E. A. Lee and D. G. Messerschmitt,
``Static Scheduling of Synchronous Data Flow Programs for Digital Signal
Processing,''
\fIIEEE Trans. Computers\fR,
Vol. C-36, No. 1, Jan 1987, pp. 24-35.

T. Lee and A. M. K. Cheng,
``Multiprocessor Scheduling of Independent Hard-Real-Time
Periodic Tasks with Task Migration Constraints,''
\fIProc. IEEE-CS Workshop on Real-Time Computing Systems
and Applications\fR, Dec. 1994.

C. L. Liu and J. W. Layland,
``Scheduling Algorithms for Multiprogramming in a Hard Real-Time
Environment,''
\fIJ. ACM\fR, Vol. 20, No. 1, Jan. 1973, pp. 46-61.

S. Ramos-Thuel and J. P. Lehoczky,
``On-Line Scheduling of Hard Deadline Aperiodic Tasks in Fixed-Priority
Systems,''
\fIProc. 14\uth\d Real-Time Systems Symposium\fR,
Raleigh-Durham, NC,
Dec. 1993.

S. Ramos-Thuel and J. P. Lehoczky,
``Algorithms for Scheduling Hard Aperiodic Tasks in
Fixed-Priority Systems using Slack Stealing,''
\fIProc. 15\uth\d Real-Time Systems Symposium\fR,
Dec. 1994.

T. Shepard and J. A. Martin Gagne,
``A Pre-Run-Time Scheduling Algorithm for
Hard Real-Time Systems,''
\fIIEEE Trans. Software Engineering,\fP
Vol. SE-17, No. 7, July 1991, pp.  669-677.

H. Tokuda, J. Wendorf, and H. Wang,
``Implementation of a Time Driven Scheduler for Real-Time Operating
Systems,''
\fIProc. 8\uth\d IEEE-CS Real-Time Systems Symp.\fR,
Dec. 1987, pp. 271-280.

W. Zhao, K. Ramamritham, and J. Stankovic,
``Scheduling Tasks with Resource Requirements in Hard Real-Time Systems,''
\fIIEEE Trans. Software Engineering\fR,
Vol. SE-13, No. 5, May 1987, pp. 564-577.

Xu. J., & Parnas, D. (1990). Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations. IEEE Trans. On Software Engineering. Vol. 16(3). (pp. 360-369). 
This paper describes static scheduling of processes with known Release Times, Deadlines, Precedence, and Exclusion Relations. 

Klara. N, & Jonathan, M. Smith(1995). The QoS Broker. IEEE Multimedia Magazine. Spring 1995 2(1),(pp. 53-67). 
This paper discusses resource orchestration by QoS brokers in networked multimedia systems. This can be applicable to other soft real-time systems. 

Lui Sha, Rajkumar Ragunathan & Shrish Sathaye (1994). Generalized Rate-Monotonic Scheduling Theory: A Framework for Developing Real-Time Systems. In Proceeding of the IEEE. Vol. 82. No. 1, Jan 1994,(pp. 68-82). 
This paper presents a good review of rate-monotonic scheduling theory and its application to real-time systems in real-life. 

Lui Sha, Rajkumar Ragunathan & Lehoczky, J. P.(1990). Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers. Vol.: 39(9). (pp. 1175 - 1185). 
This paper describes synchronization protocols in real-time systems and a priority inheritance approach to them.