Delay composition algebra: A reduction-based schedulability algebra for distributed real-time systems

Praveen Jayachandran, Tarek Abdelzaher

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper presents the delay composition algebra: a set of simple operators for systematic transformation of distributed real-time task systems into single-resource task systems such that schedulability properties of the original system are preserved. The transformation allows performing schedulability analysis on distributed systems using uniprocessor theory and analysis tools. Reduction-based analyses techniques have been used in other contexts such as control theory and circuit theory, by defining rules to compose together components of the system and reducing them into equivalent single components that can be easily analyzed. This paper is the first to develop such reduction rules for distributed real-time systems. By successively applying operators such as PIPE and SPLIT on operands that represent workload on composed subsystems, we show how a distributed task system can be reduced to an equivalent single resource task set from which the end-to-end delay and schedulability of tasks can be inferred. We show through simulations that the proposed analysis framework is less pessimistic with increasing system scale compared to traditional approaches.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 Real-Time Systems Symposium, RTSS 2008
Number of pages11
StatePublished - 2008
Event2008 Real-Time Systems Symposium, RTSS 2008 - Barcelona, Spain
Duration: Nov 30 2008Dec 3 2008

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Other2008 Real-Time Systems Symposium, RTSS 2008

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Delay composition algebra: A reduction-based schedulability algebra for distributed real-time systems'. Together they form a unique fingerprint.

Cite this