A Delay Composition Theorem for Real-Time Distributed Directed Acyclic System
Praveen Jayachandran, Tarek Abdelzaher · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2007
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.