Software Engineering Institute | Carnegie Mellon University
Software Engineering Institute | Carnegie Mellon University

Lambda-star Reasoning Frameworks

Lambda-star is a suite of performance reasoning frameworks founded on the principles of General Rate Monotonic Analysis (GRMA) [1] for predicting the average and worst-case latency of periodic and stochastic tasks in what is typified as embedded, real-time control systems.

The first to be developed in the suite was the LambdaABA reasoning framework, which focused on control systems in which all tasks are periodic, composed of components with varying priorities, and optionally including asynchronous interactions among them.

The LambdaSS reasoning framework (the second performance reasoning framework) supports predicting average-case latency of tasks having softer deadlines with stochastic (non-periodic) event interarrivals. These stochastic tasks can be part of control systems with periodic hard deadlines because their invasiveness on the hard real-time part of the system is bounded by the use of the sporadic server algorithm [2].

The LambdaWBA reasoning framework (latest in the series) predicts worst-case latency on hard real-time control systems with tasks composed of components with varying priorities, and optionally including asynchronous interactions among them.

Prediction FactsThe latest work of the PCB performance team has been addressing the predictability of systems with a mix of hard and soft real-time tasks. Whereas missing a deadline in the former can result in catastrophic failures, missing a deadline in the latter only results in a degraded quality of service (QoS). We are currently developing a reasoning framework based on Real-Time Queueing Theory (RTQT) [3] to predict latency in this class of systems.

Using Lambda-star

Lambda-star can be applied to many different, non-distributed, uniprocessor, control systems (e.g., avionic, automotive, robotic) having a mix of tasks with hard and soft deadlines with periodic and stochastic event interarrivals. Lambda-star is intended for use with a development approach that is based on prediction-enabled component technology (PECT).

Automation is central to the theme of using PECT, and the Lambda-star reasoning framework holds true to that theme. From automated interpretation to generate model representations of well-formed assemblies to automated evaluation procedures using simulations and numeric solvers, the validated Lambda-star reasoning frameworks produce predictions that can be objectively trusted.

Additional Information

Want to know more? Read about our latest work and uses of the Lambda-star reasoning frameworks.

Related Reading

Use of LambdaABA in substation automation systems

Application of LambdaSS on industrial robot control


[1] Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems
Klein, M.; Ralya, T.; Pollak, B.; Obenza, R.; & Gonzalez Harbour, M. Boston, MA: Kluwer Academic Publishers, 1993.

[2] Scheduling Sporadic and Aperiodic Events in a Hard Real-Time System
Sprunt, B.

[3] "Real-Time Queues in Heavy Traffic with Earliest-Deadline-First Queue Discipline"
Doytchinov, B.; Lehoczky, J. P.; & Shreve S.Annals of Applied Probability 11, 2 (May 2001): 332-378.