[Paper] Ensuring Data Freshness in Multi-Rate Task Chains Scheduling

Source: arXiv - 2603.09738v1

Overview

The paper tackles a subtle but critical problem in safety‑critical autonomous systems: how to keep sensor data fresh while still meeting hard real‑time deadlines. Traditional Logical Execution Time (LET) scheduling guarantees deterministic behavior, but it does so by inserting buffering latency that can cripple high‑frequency control loops. The authors propose a freshness‑aware, offset‑based scheduling framework that aligns task releases with the exact moment downstream consumers need the data, eliminating unnecessary oversampling and latency.

Key Contributions

• Freshness‑driven offset model – Introduces task offsets derived from data‑freshness constraints, enabling “just‑in‑time” data production.
• Dominant Path decomposition – Formal method to extract the most stringent data‑freshness constraints from a Data Dependency Graph (DDG) by tracing backwards from actuators.
• Consensus Offset Search algorithm – Synchronizes shared producers and private predecessors across dominant paths, guaranteeing end‑to‑end freshness without extra buffering.
• Proof of schedulability preservation – Shows that the offset‑based alignment retains the 100 % schedulability bound of Global EDF, i.e., no loss of theoretical capacity.
• Reduction of redundant sampling – Demonstrates that the approach removes the need for oversampling in multi‑rate sensor‑fusion pipelines, saving CPU and energy.

Methodology

1. Model the application as a Data Dependency Graph (DDG).

   • Nodes = tasks (sensor acquisition, fusion, control).
   • Edges = data flow with associated freshness deadlines (maximum age a datum may have when consumed).

2. Identify Dominant Paths.

   • Starting from each actuator, walk backwards through the DDG, always following the edge with the tightest freshness bound.
   • The collection of these paths captures the most time‑critical data flows.

3. Compute task offsets.

   • For each task on a dominant path, calculate the latest start time that still satisfies its downstream freshness requirement.
   • Offsets are expressed relative to a global hyperperiod, allowing tasks to be released later than in conventional LET schedules.

4. Consensus Offset Search.

   • When a task feeds multiple dominant paths (shared producer), the algorithm finds a common offset that satisfies all downstream constraints.
   • Private predecessors (tasks that only belong to one path) keep their path‑specific offsets.

5. Schedulability analysis.

   • The authors embed the computed offsets into a Global EDF (Earliest Deadline First) scheduler and prove that the feasibility region is unchanged compared to the classic LET model.

Results & Findings

• Latency reduction: By postponing data production until the exact moment it is needed, the approach cuts the effective latency by up to 66 %.
• Resource savings: Eliminating unnecessary high‑rate sampling reduces CPU load and energy consumption, which is crucial for embedded autonomous platforms.
• Theoretical guarantee: The formal proof confirms that the offset scheme does not shrink the schedulable task set under Global EDF.

Practical Implications

• Tighter control loops: Autonomous drones, robots, or driver‑assist systems can run higher‑frequency controllers without sacrificing determinism, improving stability and responsiveness.
• Simplified system integration: Engineers no longer need to manually insert “guard times” or duplicate sensor reads to meet LET constraints; the scheduler handles freshness automatically.
• Power‑constrained devices: IoT edge nodes that fuse multi‑rate sensor data (e.g., LiDAR + IMU) can lower duty cycles, extending battery life.
• Toolchain impact: Existing EDF‑based real‑time operating systems (e.g., FreeRTOS‑Plus, LITMUS^RT) could incorporate the Consensus Offset Search as a preprocessing step, making freshness‑aware scheduling a drop‑in feature.

Limitations & Future Work

• Assumption of static task sets: The analysis presumes a fixed set of periodic tasks; dynamic task creation (common in perception pipelines) would need extensions.
• Single‑processor focus: While the proof holds for Global EDF on a single multiprocessor platform, scaling to heterogeneous cores (GPU, DSP) is left for later research.
• Tool support: The authors provide a prototype implementation but no open‑source integration with mainstream RTOSes yet.
• Future directions: Exploring adaptive offset recomputation at runtime, handling aperiodic high‑priority interrupts, and extending the model to probabilistic freshness guarantees.

Authors

• José Luis Conradi Hoffmann
• Antônio Augusto Fröhlich

Paper Information

• arXiv ID: 2603.09738v1
• Categories: cs.OS, cs.DC
• Published: March 10, 2026
• PDF: Download PDF