Reduction-based schedulability analysis of distributed systems with cycles in the task graph

Praveen Jayachandran, Tarek Abdelzaher

Research output: Contribution to journalArticlepeer-review


A significant problem with no simple solutions in current real-time literature is analyzing the end-to-end schedulability of tasks in distributed systems with cycles in the task graph. Prior approaches including network calculus and holistic schedulability analysis work best for acyclic task flows. They involve iterative solutions or offer no solutions at all when flows are non-acyclic. This paper demonstrates the construction of the first generalized closed-form expression for schedulability analysis in distributed task systems with non-acyclic flows. The approach is a significant extension to our previous work on schedulability in Directed Acyclic Graphs. Our main result is a bound on end-to-end delay for a task in a distributed system with non-acyclic task flows. The delay bound allows one of several schedulability tests to be performed. Using the end-to-end delay bound, we extend the delay composition algebra developed for acyclic distributed systems in prior work, to handle loops in the task graph as well. Evaluation shows that the schedulability tests thus constructed are less pessimistic than prior approaches for large distributed systems.

Original languageEnglish (US)
Pages (from-to)121-151
Number of pages31
JournalReal-Time Systems
Issue number1
StatePublished - Sep 2010


  • End-to-end delay
  • Non-acyclic systems
  • Problem reduction
  • Real-time distributed system
  • Schedulability analysis

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering


Dive into the research topics of 'Reduction-based schedulability analysis of distributed systems with cycles in the task graph'. Together they form a unique fingerprint.

Cite this