CS Paper Radar

Response Time Stochastic Analysis for Fixed-Priority Stable Real-Time Systems

Kevin Zagalo, Yasmina Abdeddaïm, Avner Bar-Hen, Liliana Cucu-Grosjean

eess.SY math.PR ·submitted 2026-09-18 13:30 UTC · v1
top venuetheoryhighly cited

Abstract

In this paper, we prove that a mean system utilization smaller than one is a necessary condition for the feasibility of real-time systems. Such systems are defined as stable. Stable systems have two distinct states: a transient state, followed by a steady-state where the same distribution of response times is repeated infinitely for each task. We prove that the Liu and Layland theorem holds for stable probabilistic real-time systems with implicit deadlines, we provide an analytical approximation of response times for each of those two states and a bound of the instant when a real-time system becomes steady.

Journal ref
IEEE Transactions on Computers ( Volume: 72, Issue: 1, 01 January 2023)
DOI
10.1109/TC.2022.3211421

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Preemption: Guaranteeing Information Freshness in Mean Age and Beyond

cs.IT ·2026-11-19 ·Aimin Li, Yiğit İnce, Elif Uysal
theory similarity 0.53
Abstract · 21 pages. Submitted to IEEE/ACM Transactions on Networking. Journal extension of the ISIT 2026 paper arXiv:2601.16624

Once a status update enters service, age-optimal policies must wait for it, even when heavy-tailed delays inflate the Age of Information (AoI). We develop a framework in which the sender may preempt the update in service and sample a fresh one, under general service-time distributions and explicit action costs. Our framework covers sources that generate updates at will as well as random update arrivals. Under nondecreasing age costs, we prove that, with preemption, a finite mean delay suffices for a finite average age even under infinite delay variance. We show the optimality of constant service-age thresholds from prior work for exponential service, and exhibit numerically that for general delays the optimal preemption rule depends on both the AoI and the elapsed service time. Under an action-cost budget, we further minimize the Value at Risk (VaR), which bounds the AoI except for a prescribed fraction of time, and the Conditional Value at Risk (CVaR), the mean AoI over that fraction. We reduce both to the same optimality equations without enlarging the state space. Under Pareto and log-normal delays, our algorithm TAILOR keeps the average cost bounded as delay variance grows, while optimal non-preemptive sampling diverges. With optimal preemption, a more variable network can allow fresher data than a steadier one of equal mean delay.

0.30

Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous Feedback

cs.IT cs.NIeess.SY ·2026-11-16 ·Subhankar Banerjee, Sennur Ulukus
theory similarity 0.52
Abstract

We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability $q$, subject to average sampling- and transmission-rate constraints $f_s$ and $f_r$, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a $4$-approximation guarantee. The joint problem reduces to the sampling-constrained problem when $f_s\leq qf_r$ and the transmission-constrained problem when $f_s\geq f_r$. For $qf_r<f_s<f_r$, we formulate a constrained Markov decision process (CMDP) and introduce the class $\barΠ$ of $(W,R)$ policies, where $W$ specifies a waiting threshold for transmission and $R$ specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in $\barΠ$. We then formulate a linear program (LP) over distributions of $(W,R)$ policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three $(W,R)$ policies. Since $\barΠ$ is countably infinite, for every $ε>0$ we construct a finite subset $\barΠ_ε\subset\barΠ$ and show that the LP restricted to this set yields an $ε$-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four $(W,R)$ policies with a $2$-approximation guarantee for $qf_r<f_s<f_r$.

0.12

Stochastic Aggregation with Prescribed Resources and Additive Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.52
Abstract

We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served $t$ units of time after its arrival incurs delay cost $t$. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource--scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below $2.113$. The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.

0.17

Analysis of Triggered Packet Streams: Stochastic Bounds on System Time under General Triggering Delays

cs.PF math.PR ·2026-10-29 ·Mehran Rahnamania, Michel Mandjes, Farid Ashtiani
theory similarity 0.51
Abstract

Many emerging communication systems increasingly involve devices that transmit packets in multiple causally dependent stages as part of an internal workflow, rather than waiting for receiver feedback. To analyze such systems, we recently introduced the $\mathrm{M^T/G/1}$ queue, in which primary customers arrive according to an exogenous Poisson process, and each triggers a secondary customer to join the queue after an independent random delay, called the \textit{triggering delay}. Our prior heuristic approximations assume identical exponential service times, and our matrix-analytic framework assumes exponential triggering delays. However, no exact analysis is available when both distributions are general. In this paper, we derive stochastic bounds, in the usual stochastic order, on the system-time distribution of each customer class under general triggering-delay and service-time distributions. The service times within each primary--secondary pair may be generally dependent. Using sample-path coupling and level-crossing arguments, we show that the stationary workload is stochastically sandwiched between those of two classical queues: a two-class $\mathrm{M/G/1}$ queue with independent Poisson arrivals (lower bound), and a batch-arrival $\mathrm{M^{[2]}/G/1}$ queue where each primary--secondary pair arrives simultaneously (upper bound). Notably, these bounds do not depend on the triggering-delay distribution, and they are asymptotically tight in the sense that the stationary workload converges in distribution to that of the lower- and upper-bound queues as the triggering delays diverge to infinity and converge to zero in probability, respectively. We translate these workload bounds into system-time bounds for each customer class. Simulation experiments support these bounds.

0.08

Threshold Structure of Optimal Policies in Restart POMDPs

cs.LG math.OCmath.PR ·2026-08-11 ·Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang
publishedtheory similarity 0.51
Abstract · 8 pages, the paper has been accepted to IEEE CDC 2026

We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

0.25

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.50
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Adaptive Handling of Deadline Misses via Stochastic MPC

eess.SY ·2026-10-13 ·Melanie Gallant, Paolo Pazzaglia, Christoph Mark, Kevin Schmidt, Martina Maggio
similarity 0.50
Abstract

Real-time control systems may experience sporadic computational overloads that cause controller executions to overrun their expected deadlines, affecting the timely update of control inputs. Such overruns are classically handled with static decisions, e.g., by either stopping and discarding the late execution at the deadline instant, or continuing it while skipping the next activations. This paper first demonstrates that such static policies can lead to suboptimal performance when the controlled system undergoes varying operating conditions, and thus proposes a control-driven hybrid overrun strategy that optimally adapts the deadline miss handling at runtime. We model the closed loop as a Markov jump linear system, whose modes encode overrun histories, and we formulate a scenario-tree-based stochastic model predictive control problem that predicts and optimizes over possible sequences of deadline hits and misses. We evaluate our proposal on linear benchmarks including a double integrator and an aircraft pitch system.

0.28

Self-stabilising approximate clock synchronisation requires linear time

cs.DC ·2026-11-03 ·Joel Rybicki
theory similarity 0.50
Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

0.14