Acyclic tasks have been analyzed to death. When cycles are added to any task graph, practically all forms of analysis fall apart. Hence, most research tends to focus on forming upper bounds on some metric, whether it’s schedulability, throughput, utilization, or some other domain-specific criterion.

The authors claim that this paper is “the first generalized closed-form expression for schedulability analysis in distributed task systems with non-acyclic flows.” However, some might contest the words “first” and “generalized” in this statement. This review abstains from such an evaluation--feel free to form your own opinions--and instead provides a brief outline of the paper.

After a brief overview of related work, the authors present their model for computing an upper bound on task completion time, given limited resource nodes in the presence of other tasks, where any task can have cycles in its node usage graph. Tasks can have different priority levels, and the majority of proofs and descriptions assume preemptive scheduling; still, the authors also show the corresponding results when tasks are nonpreemptive.

A very simplistic summary would be that, by breaking up cyclic tasks into acyclic segments, a narrower upper bound can be obtained if it is shown that only some stages of a task affect the deadlines of stages of other tasks. The model is shown (through simulation) to compare favorably with the traditional method that “breaks ... each task into per-stage deadlines and analyzes each stage independently,” as well as to “an iterative procedure to converge to worst-case response time values at each stage for every task.”

The authors then add loops to their previously developed delay composition algebra [1]. These final two sections are the most challenging to decipher. As such, readers should augment their reading with the authors’ previous work.