On the tractability of digraph-based task models

Martin Stigge, Pontus Ekberg, Nan Guan, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

25 Citations (Scopus)


In formal analysis of real-time systems, a major concern is the analysis efficiency. As the expressiveness of models grows, so grows the complexity of their analysis. A recently proposed model, the digraph real-time task model (DRT), offers high expressiveness well beyond traditional periodic task models. Still, the associated feasibility problem on preemptive uniprocessors remains tractable. It is an open question to what extent the expressiveness of the model can be further increased before the feasibility problem becomes intractable. In this paper, we study that tractability border. We show that system models with the need for global timing constraints make feasibility analysis intractable. However, our second technical result shows that it remains tractable if the number of global constraints is bounded by a constant. Thus, this paper establishes a precise borderline between tractability and intractability.
Original languageEnglish
Title of host publicationProceedings of the 23rd Euromicro Conference on Real-Time Systems, ECRTS 2011
Number of pages10
Publication statusPublished - 26 Sep 2011
Externally publishedYes
Event23rd Euromicro Conference on Real-Time Systems, ECRTS 2011 - Porto, Portugal
Duration: 5 Jul 20118 Jul 2011


Conference23rd Euromicro Conference on Real-Time Systems, ECRTS 2011


  • feasibility
  • real-time task models
  • schedulability
  • tractability

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this