pith. sign in

arxiv: 2604.09102 · v1 · submitted 2026-04-10 · 📡 eess.SY · cs.SY

Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

Pith reviewed 2026-05-10 16:48 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords cause-effect chainstiming anomaliesend-to-end latencydeterministic data flowreal-time schedulingworst-case latencylatency bounds
0
0 comments X

The pith

Scheduling cause-effect chains with deterministic data flow eliminates timing anomalies in end-to-end latency with negligible impact on average performance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper identifies two fundamental causes of timing anomalies that can make end-to-end latency in cause-effect chains increase when some task times decrease. It introduces Deterministic Data Flow as a new scheduling approach to remove these anomalies entirely. This method preserves nearly all of the original average latency while allowing a precise calculation of the maximum latency based solely on worst-case execution times. Experiments confirm reductions in peak latency, average latency, and variation compared to existing techniques.

Core claim

Two basic causes of timing anomalies exist in end-to-end latency analysis for cause-effect chains. Using Deterministic Data Flow eliminates these anomalies, as formally proven, so that the upper bound on latency equals the latency computed when every job runs at its worst-case execution time.

What carries the argument

Deterministic Data Flow (DDF), which enforces a fixed pattern of data propagation between tasks to prevent the identified causes of timing anomalies.

If this is right

  • Precise upper bounds on end-to-end latency become available without over-approximation due to anomalies.
  • Systems can achieve lower maximum latency while maintaining close to original average latency.
  • Latency jitter decreases compared to state-of-the-art methods.
  • Analysis simplifies because worst-case latency is directly computable from worst-case execution times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If DDF can be implemented without extra hardware, it may extend to resource-constrained embedded devices.
  • Similar deterministic constraints could address anomalies in other multi-task latency analyses beyond cause-effect chains.
  • Adoption might allow tighter timing budgets in safety-critical applications like vehicle control systems.

Load-bearing premise

The two identified causes account for every possible timing anomaly that can occur in cause-effect chains under conventional real-time scheduling models.

What would settle it

A concrete schedule using Deterministic Data Flow in which shortening the execution time of one job causes the end-to-end latency to increase.

Figures

Figures reproduced from arXiv: 2604.09102 by Bo Zhang, Caixu Zhao, Cheng Tang, Haoyuan Ren, Lei Gong, Teng Wang, Wenqi Lou, Xi Li, Yinkang Gao, Yixuan Zhu.

Figure 1
Figure 1. Figure 1: Timing anomaly in the data propagation of CE [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Mechanism of the RAW and RFI for the DDF [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: MRT ratio for Our/M23 in various 𝛼 and 𝑈 when 𝑆 is the all-WCET schedule 𝑆𝑊 . So, max{ℓ( −→𝑖𝑎𝑐𝑚 𝐸,𝑆 ) | 𝑆 ∈ S} = ℓ( −→𝑖𝑎𝑐𝑚 𝐸,𝑆𝑊 ). Therefore, it follows that: 𝑀𝑅𝑇 (𝐸) = 𝑀𝑅𝑇 (𝐸, 𝑆𝑊 ). Thm 5.4 is thus proven, implying that TA-free for MRT. □ The same method can be applied and proved TA-free for MDA. 6 Experiment Evaluation The end-to-end latency is critical for verifying the timing behavior of CE chains in a… view at source ↗
Figure 5
Figure 5. Figure 5: Online average reaction time 0.2 0.4 0.6 0.8 BCET factor 0.0 0.1 0.2 0.3 0.4 0.5 Jitter ratio 0.47 0.44 0.39 0.32 Average reaction time jitter ratio: Our/M23 [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
read the original abstract

In real-time systems, both individual task execution and data propagation must meet strict timing constraints. Cause-effect (CE) chains are widely used to analyze such behaviors by end-to-end latency. However, timing anomalies (TAs) can distort it, where a local reduction in execution times leads to an increase in the overall end-to-end latency. As a result, precisely analyzing the upper bounds of the latency becomes challenging, and such systems typically exhibit larger upper bounds than TA-eliminated systems. Existing studies either eliminate TAs by completely sacrificing average latency to simplify analysis or, despite adopting complex safe analysis methods, do not eliminate TAs effectively, still having high latencies. To address this issue, we identify two basic causes of TAs in end-to-end latency. Based on these causes, we propose the first treatment that eliminates TAs in the latency with negligible average latency loss using Deterministic Data Flow (DDF). We further formally prove its TA-free property. Therefore, we can get a precise upper bound for latency when all jobs execute with their worst-case execution times. Experimental results show that it effectively reduces the maximum end-to-end latency, the average latency, and latency jitter compared with the state-of-the-art (SOTA) method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper identifies two basic causes of timing anomalies (TAs) in end-to-end latency analysis of cause-effect chains under real-time task models. It proposes Deterministic Data Flow (DDF) as a scheduling treatment that eliminates TAs while incurring only negligible average latency overhead, formally proves the TA-free property of DDF, and thereby obtains a precise upper bound on latency when all jobs execute at their worst-case execution times. Experiments are reported to show reductions in maximum end-to-end latency, average latency, and latency jitter relative to the state-of-the-art.

Significance. If the exhaustiveness of the two TA causes and the formal proof hold, the result would be significant for real-time systems: it would allow tighter, WCET-based latency bounds for CE chains without the usual penalties of either inflated average latency or overly conservative analysis methods. The approach could improve predictability in safety-critical applications that rely on end-to-end latency guarantees.

major comments (2)
  1. [Abstract / Identification of TA causes] Abstract and the section identifying the causes of TAs: the claim that the two identified causes are exhaustive for all cause-effect chains under standard real-time task models is load-bearing for the central guarantee that DDF eliminates every possible TA and yields a precise upper bound. No exhaustive case analysis, reduction to a known complete set of anomalies, or consideration of interactions such as priority inheritance, shared-resource contention, or release jitter is provided to substantiate exhaustiveness.
  2. [Formal proof section] The formal proof of the TA-free property (asserted in the abstract): the proof is stated to exist but its assumptions on the task model, the precise modeling of DDF constraints, and the induction or case analysis used to show that no TA can arise are not visible. Without these details the claim that a precise WCET-based upper bound follows cannot be verified.
minor comments (2)
  1. [Experimental evaluation] Experimental results are summarized without reporting the task-set generation method, number of task sets, baseline implementations, hardware platform, or quantitative values for the claimed reductions and 'negligible' average-latency loss; these details are needed for reproducibility.
  2. [DDF definition] The manuscript should clarify whether DDF introduces additional precedence or synchronization constraints beyond standard task models and whether any hardware support is required.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough and constructive review. The comments on the exhaustiveness of the identified timing anomaly causes and the visibility of the formal proof are well taken. We will revise the manuscript to strengthen these aspects while preserving the core contribution.

read point-by-point responses
  1. Referee: [Abstract / Identification of TA causes] Abstract and the section identifying the causes of TAs: the claim that the two identified causes are exhaustive for all cause-effect chains under standard real-time task models is load-bearing for the central guarantee that DDF eliminates every possible TA and yields a precise upper bound. No exhaustive case analysis, reduction to a known complete set of anomalies, or consideration of interactions such as priority inheritance, shared-resource contention, or release jitter is provided to substantiate exhaustiveness.

    Authors: We acknowledge that a clear justification of exhaustiveness is necessary to support the claim that DDF eliminates all TAs. In the revised version we will insert a dedicated subsection that enumerates potential additional sources of anomalies (priority inheritance, shared-resource contention, release jitter) and shows, via reduction arguments, that each either reduces to one of the two basic causes or is prevented from producing a new TA under the DDF constraints. This addition will make the exhaustiveness argument explicit without changing the technical results. revision: yes

  2. Referee: [Formal proof section] The formal proof of the TA-free property (asserted in the abstract): the proof is stated to exist but its assumptions on the task model, the precise modeling of DDF constraints, and the induction or case analysis used to show that no TA can arise are not visible. Without these details the claim that a precise WCET-based upper bound follows cannot be verified.

    Authors: The manuscript contains a formal proof, yet we agree that its presentation can be made more self-contained. In the revision we will expand the proof section to (i) state all task-model assumptions explicitly, (ii) give a precise mathematical definition of the DDF scheduling constraints, and (iii) detail the induction (or case analysis) that establishes the absence of timing anomalies, thereby confirming that the end-to-end latency is bounded by the WCET-based analysis. The expanded proof will be placed in the main text or a clearly referenced appendix. revision: yes

Circularity Check

0 steps flagged

No circularity detected in derivation chain

full rationale

The abstract and described claims identify two basic causes of timing anomalies, propose DDF based on them, and state a formal proof of the TA-free property leading to a precise WCET-based upper bound. No equations, self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations appear that would reduce the claimed bound or proof to the inputs by construction. The proof is presented as independent formal verification, and the result does not rely on renaming known patterns or smuggling ansatzes via citation. This is a self-contained analysis against external benchmarks of scheduling anomalies.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Only abstract available; ledger populated from implied domain context.

axioms (1)
  • domain assumption Standard real-time task model with periodic tasks, worst-case execution times, and cause-effect chain data dependencies.
    Invoked by references to WCET, end-to-end latency, and scheduling without further justification.
invented entities (1)
  • Deterministic Data Flow (DDF) no independent evidence
    purpose: Scheduling mechanism to eliminate timing anomalies in CE-chain latency.
    New construct introduced by the paper; no independent evidence supplied.

pith-pipeline@v0.9.0 · 5552 in / 1136 out tokens · 41166 ms · 2026-05-10T16:48:44.646712+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Reaction time analysis of event-triggered processing chains with data refreshing

    Yue Tang, Nan Guan, Xu Jiang, Zheng Dong, and Wang Yi. Reaction time analysis of event-triggered processing chains with data refreshing. In2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2023

  2. [2]

    Analysis and optimization of worst-case time disparity in cause-effect chains

    Xu Jiang, Xiantong Luo, Nan Guan, Zheng Dong, Shaoshan Liu, and Wang Yi. Analysis and optimization of worst-case time disparity in cause-effect chains. In 2023 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1–6. IEEE, 2023

  3. [3]

    Tsi: A time-semantic instruction set for determin- istic data-flow execution in real-time embedded systems

    Yinkang Gao, Bo Zhang, Yixuan Zhu, Lei Gong, Teng Wang, Wenqi Lou, Chao Wang, Xi Li, and Xuehai Zhou. Tsi: A time-semantic instruction set for determin- istic data-flow execution in real-time embedded systems. In2025 IEEE Real-Time Systems Symposium (RTSS), pages 514–527, 2025

  4. [4]

    Data-flow availability: Achieving timing assurance in autonomous systems

    Ao Li and Ning Zhang. Data-flow availability: Achieving timing assurance in autonomous systems. In18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 445–463, 2024

  5. [5]

    Period optimization for hard real-time distributed automotive systems

    Abhijit Davare, Qi Zhu, Marco Di Natale, Claudio Pinello, Sri Kanajan, and Al- berto Sangiovanni-Vincentelli. Period optimization for hard real-time distributed automotive systems. InProceedings of the 44th annual Design Automation Confer- ence, pages 278–283, 2007

  6. [6]

    Opti- mizing end-to-end latencies by adaptation of the activation events in distributed automotive systems

    AS Vincentelli, Paolo Giusto, Claudio Pinello, Wei Zheng, and MD Natale. Opti- mizing end-to-end latencies by adaptation of the activation events in distributed automotive systems. In13th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS’07), pages 293–302. IEEE, 2007

  7. [7]

    Optimization of task allocation and priority assignment in hard real- time distributed systems.ACM Transactions on Embedded Computing Systems (TECS), 11(4):1–30, 2013

    Qi Zhu, Haibo Zeng, Wei Zheng, Marco DI Natale, and Alberto Sangiovanni- Vincentelli. Optimization of task allocation and priority assignment in hard real- time distributed systems.ACM Transactions on Embedded Computing Systems (TECS), 11(4):1–30, 2013

  8. [8]

    Communication centric design in complex automotive embedded systems

    Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst. Communication centric design in complex automotive embedded systems. In29th Euromicro Conference on Real-Time Systems (ECRTS 2017), pages 10–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017

  9. [9]

    End-to-end timing analysis in ros2

    Harun Teper, Mario Günzel, Niklas Ueter, Georg von der Brüggen, and Jian- Jia Chen. End-to-end timing analysis in ros2. In2022 IEEE Real-Time Systems Symposium (RTSS), pages 53–65. IEEE, 2022

  10. [10]

    Timing analysis of asynchronized distributed cause-effect chains

    Mario Günzel, Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, Marco Dürr, and Jian-Jia Chen. Timing analysis of asynchronized distributed cause-effect chains. In2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 40–52. IEEE, 2021

  11. [11]

    Compositional timing analysis of asynchronized dis- tributed cause-effect chains.ACM Transactions on Embedded Computing Systems, 22(4):1–34, 2023

    Mario Günzel, Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, Marco Dürr, and Jian-Jia Chen. Compositional timing analysis of asynchronized dis- tributed cause-effect chains.ACM Transactions on Embedded Computing Systems, 22(4):1–34, 2023

  12. [12]

    Synthesizing job-level dependencies for automotive multi-rate effect chains

    Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. Synthesizing job-level dependencies for automotive multi-rate effect chains. In2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 159–169, 2016

  13. [13]

    End- to-end latency of cause-effect chains: a tutorial.ACM Transactions on Embedded Computing Systems, 24(1):1–18, 2024

    Mario Guenzel, Harun Teper, Georg von der Brüggen, and Jian-jia Chen. End- to-end latency of cause-effect chains: a tutorial.ACM Transactions on Embedded Computing Systems, 24(1):1–18, 2024

  14. [14]

    Tti: An instruction set supporting priority-inversion-free time-triggered preemptive scheduling in real-time embedded systems

    Yinkang Gao, Yixuan Zhu, Bo Zhang, Haoyuan Ren, Cheng Tang, and Xi Li. Tti: An instruction set supporting priority-inversion-free time-triggered preemptive scheduling in real-time embedded systems. In2026 31st Asia and South Pacific Design Automation Conference (ASP-DAC), pages 1035–1041, 2026

  15. [15]

    Timing- anomaly free dynamic scheduling of conditional dag tasks on multi-core systems

    Peng Chen, Weichen Liu, Xu Jiang, Qingqiang He, and Nan Guan. Timing- anomaly free dynamic scheduling of conditional dag tasks on multi-core systems. ACM Trans. Embed. Comput. Syst., 18(5s), October 2019

  16. [16]

    Timing-anomaly free dynamic scheduling of periodic dag tasks with non-preemptive nodes

    Gaoyang Dai, Morteza Mohaqeqi, and Wang Yi. Timing-anomaly free dynamic scheduling of periodic dag tasks with non-preemptive nodes. In2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 119–128. IEEE, 2021

  17. [17]

    Scheduling periodic segmented self-suspending tasks without timing anomalies

    Ching-Chi Lin, Mario Günzel, Junjie Shi, Tristan Taylan Seidl, Kuan-Hsun Chen, and Jian-Jia Chen. Scheduling periodic segmented self-suspending tasks without timing anomalies. In2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 161–173. IEEE, 2023

  18. [18]

    Ronald L. Graham. Bounds on multiprocessing timing anomalies.SIAM journal on Applied Mathematics, 17(2):416–429, 1969

  19. [19]

    Timing-anomaly free dy- namic scheduling of task-based parallel applications

    Petros Voudouris, Per Stenström, and Risat Pathan. Timing-anomaly free dy- namic scheduling of task-based parallel applications. In2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 365–376. IEEE, 2017

  20. [20]

    Quasi-static scheduling for deterministic timed concurrent models on multi-core hardware

    Shaokai Lin, Erling Jellum, Mirco Theile, Tassilo Tanneberger, Binqi Sun, Chadlia Jerad, Yimo Xu, Guangyu Feng, Magnus Mæhlum, Jian-Jia Chen, et al. Quasi-static scheduling for deterministic timed concurrent models on multi-core hardware. ACM Transactions on Embedded Computing Systems, 24(5s):1–25, 2025

  21. [21]

    A survey of timing verification techniques for multi-core real-time systems.ACM Computing Surveys (CSUR), 52(3):1–38, 2019

    Claire Maiza, Hamza Rihani, Juan M Rivas, Joël Goossens, Sebastian Altmeyer, and Robert I Davis. A survey of timing verification techniques for multi-core real-time systems.ACM Computing Surveys (CSUR), 52(3):1–38, 2019

  22. [22]

    Semantics- preserving multitask implementation of synchronous programs.ACM Transac- tions on Embedded Computing Systems (TECS), 7(2):1–40, 2008

    Paul Caspi, Norman Scaife, Christos Sofronis, and Stavros Tripakis. Semantics- preserving multitask implementation of synchronous programs.ACM Transac- tions on Embedded Computing Systems (TECS), 7(2):1–40, 2008

  23. [23]

    End- to-end timing analysis of sporadic cause-effect chains in distributed systems

    Marco Dürr, Georg Von Der Brüggen, Kuan-Hsun Chen, and Jian-Jia Chen. End- to-end timing analysis of sporadic cause-effect chains in distributed systems. ACM Transactions on Embedded Computing Systems (TECS), 18(5s):1–24, 2019

  24. [24]

    Optimizing utilization in logical execution time system with pre- served externally-observable timed i/o semantics.Journal of Systems Architecture, page 103589, 2025

    Bo Zhang, Caixu Zhao, Yinkang Gao, Yixuan Zhu, Lei Gong, Teng Wang, Wenqi Lou, and Xi Li. Optimizing utilization in logical execution time system with pre- served externally-observable timed i/o semantics.Journal of Systems Architecture, page 103589, 2025

  25. [25]

    On the equivalence of maximum reaction time and maximum data age for cause-effect chains

    Mario Günzel, Harun Teper, Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen. On the equivalence of maximum reaction time and maximum data age for cause-effect chains. In35th Euromicro Conference on Real-Time Systems, DAC ’26, July 26–29, 2026, Long Beach, CA, USA Zhu et al. ECRTS 2023, pages 10–1. Dagstuhl, 2023

  26. [26]

    Generalized multiframe tasks.Real-Time Systems, 17(1):5–22, 1999

    Sanjoy Baruah, Deji Chen, Sergey Gorinsky, and Aloysius Mok. Generalized multiframe tasks.Real-Time Systems, 17(1):5–22, 1999

  27. [27]

    A multiframe model for real-time tasks.IEEE transactions on Software Engineering, 23(10):635–645, 2002

    Aloysius K Mok and Deji Chen. A multiframe model for real-time tasks.IEEE transactions on Software Engineering, 23(10):635–645, 2002

  28. [28]

    Real world automotive benchmarks for free

    Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In6th International Workshop on Analysis Tools and Method- ologies for Embedded and Real-time Systems (W ATERS), volume 130, page 43, 2015

  29. [29]

    Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints

    Patrick Cousot and Radhia Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. InProceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 238–252, 1977

  30. [30]

    A definition and classification of timing anom- alies

    Jan Reineke, Björn Wachter, Stefan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anom- alies. In6th International Workshop on Worst-Case Execution Time Analysis (WCET’06)(2006), pages 1–6. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2006

  31. [31]

    Timing anomalies in dynamically sched- uled microprocessors

    Thomas Lundqvist and Per Stenstrom. Timing anomalies in dynamically sched- uled microprocessors. InProceedings 20th IEEE Real-Time Systems Symposium (Cat. No. 99CB37054), pages 12–21. IEEE, 1999

  32. [32]

    The role of causality in a formal definition of timing anomalies

    Benjamin Binder, Mihail Asavoae, Florian Brandner, Belgacem Ben Hedia, and Mathieu Jan. The role of causality in a formal definition of timing anomalies. In 2022 IEEE 28th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 91–102, 2022

  33. [33]

    Is this still normal? putting definitions of timing anomalies to the test

    Benjamin Binder, Mihail Asavoae, Belgacem Ben Hedia, Florian Brandner, and Mathieu Jan. Is this still normal? putting definitions of timing anomalies to the test. In2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 139–148. IEEE, 2021

  34. [34]

    What is a timing anomaly? In12th International Workshop on Worst-Case Execution Time Analysis (2012), pages 1–12

    Franck Cassez, René Rydhof Hansen, and Mads Chr Olesen. What is a timing anomaly? In12th International Workshop on Worst-Case Execution Time Analysis (2012), pages 1–12. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2012

  35. [35]

    Work-in-progress: A timing-anomaly free dynamic scheduling on heterogeneous systems

    Yixuan Zhu, Yinkang Gao, Binze Jiang, Xiaohang Gong, Lei Gong, Chao Wang, Xi Li, and Xuehai Zhou. Work-in-progress: A timing-anomaly free dynamic scheduling on heterogeneous systems. In2025 IEEE Real-Time Systems Symposium (RTSS), pages 620–623, 2025