Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency
Pith reviewed 2026-05-10 16:48 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- [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.
- [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)
- [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.
- [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
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
-
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
-
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
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
axioms (1)
- domain assumption Standard real-time task model with periodic tasks, worst-case execution times, and cause-effect chain data dependencies.
invented entities (1)
-
Deterministic Data Flow (DDF)
no independent evidence
Reference graph
Works this paper leans on
-
[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
work page 2023
-
[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
work page 2023
-
[3]
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
work page 2025
-
[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
work page 2024
-
[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
work page 2007
-
[6]
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
work page 2007
-
[7]
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
work page 2013
-
[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
work page 2017
-
[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
work page 2022
-
[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
work page 2021
-
[11]
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
work page 2023
-
[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
work page 2016
-
[13]
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
work page 2024
-
[14]
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
work page 2026
-
[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
work page 2019
-
[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
work page 2021
-
[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
work page 2023
-
[18]
Ronald L. Graham. Bounds on multiprocessing timing anomalies.SIAM journal on Applied Mathematics, 17(2):416–429, 1969
work page 1969
-
[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
work page 2017
-
[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
work page 2025
-
[21]
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
work page 2019
-
[22]
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
work page 2008
-
[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
work page 2019
-
[24]
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
work page 2025
-
[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
work page 2026
-
[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
work page 1999
-
[27]
Aloysius K Mok and Deji Chen. A multiframe model for real-time tasks.IEEE transactions on Software Engineering, 23(10):635–645, 2002
work page 2002
-
[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
work page 2015
-
[29]
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
work page 1977
-
[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
work page 2006
-
[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
work page 1999
-
[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
work page 2022
-
[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
work page 2021
-
[34]
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
work page 2012
-
[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
work page 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.