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

Jayachandran, Praveen; Abdelzaher, Tarek F.

Permalink

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

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