University of Illinois Urbana-Champaign

A Delay Composition Theorem for Real-Time Distributed Directed Acyclic System

Jayachandran, Praveen; Abdelzaher, Tarek F.

Content Files
A Delay Composition Theorem for Real-Time Distributed Directed Acyclic System.pdf

Permalink

https://hdl.handle.net/2142/11331

Description

Title
A Delay Composition Theorem for Real-Time Distributed Directed Acyclic System
Author(s)
  • Jayachandran, Praveen
  • Abdelzaher, Tarek F.
Issue Date
2007-05
Keyword(s)
distributed systems
Date of Ingest
2009-04-22T15:08:16Z
Abstract
In this paper, we present a delay composition rule that bounds the worst-case end-to-end delay of a job as a function of per-stage execution times of higher priority jobs along its path, in a multistage distributed system where the routes of jobs form a directed acyclic graph. The delay composition rule makes no assumption on scheduling policy (except that jobs are assigned the same priority on all stages), and makes no assumption on periodicity. Applying the rule to a particular job only requires knowledge of execution times of higher priority jobs along the path followed by the job, which is in contrast with traditional schedulability analysis techniques that require global knowledge of all jobs and routes in the distributed system, which may be difficult or expensive to obtain. Inspired by the resulting simple delay expression of our composition rule, a transformation of the system to an equivalent single stage system becomes apparent. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide schedulability of tasks in a DAG. We compare our analysis technique with traditional techniques using simulations.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11331
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY