Files in this item



application/pdfA Delay Composi ... irected Acyclic System.pdf (220kB)
(no description provided)PDF


Title:A Delay Composition Theorem for Real-Time Distributed Directed Acyclic System
Author(s):Jayachandran, Praveen; Abdelzaher, Tarek F.
Subject(s):distributed systems
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.
Issue Date:2007-05
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2007-2851
Rights 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).
Date Available in IDEALS:2009-04-22

This item appears in the following Collection(s)

Item Statistics