pith. sign in

arxiv: 1907.05408 · v1 · pith:X6JQJN5Hnew · submitted 2019-07-11 · 💻 cs.IT · cs.NI· eess.SP· math.IT

Timely Cloud Computing: Preemption and Waiting

Ahmed Arafa , Roy D. Yates , H. Vincent Poor This is my paper

Pith reviewed 2026-05-24 22:44 UTC · model grok-4.3

classification 💻 cs.IT cs.NIeess.SPmath.IT
keywords age of informationpreemptioncloud computingstatus updatingwaiting policyexponential service timesAoI minimization
0
0 comments X

The pith

A threshold waiting policy with preemption of late computations minimizes long-term average age of information in cloud status updates.

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

The paper investigates scheduling of sensor measurements and their cloud computations to keep a monitor supplied with fresh results, using the age of information metric. It establishes that the optimal stationary deterministic policy waits after an update until the age exceeds a threshold before acquiring the next measurement, with the threshold depending on the service time distribution and a fixed cutoff time for preemption. The cutoff time is optimized explicitly for standard and shifted exponential service times. Preemption of computations whose service time exceeds the cutoff reduces average age more effectively than waiting policies alone. The analysis covers the long-term average age under these policies.

Core claim

The optimal waiting policy that minimizes the long term average AoI has a threshold structure, in which a new measurement is uploaded following an update only if the AoI grows above a certain threshold that is a function of the service time distribution and the cutoff time. The optimal cutoff is then found for standard and shifted exponential service times. While waiting before updating can be beneficial for AoI, preemption of late updates can be even more beneficial.

What carries the argument

The threshold-structured waiting policy combined with a fixed cutoff time for preemption of service times.

If this is right

  • The long-term average AoI is minimized by waiting until AoI exceeds a distribution-dependent threshold before the next upload.
  • Optimal cutoff times exist in closed form for both standard and shifted exponential service distributions.
  • Preemption of updates whose service exceeds the cutoff yields lower average AoI than pure waiting policies without preemption.
  • The policy structure holds for any service time distribution when the cutoff is given.

Where Pith is reading between the lines

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

  • The threshold structure may generalize to non-stationary or randomized policies if the optimality proof can be extended.
  • Similar preemption cutoffs could reduce age in multi-server cloud setups or with correlated service times.
  • The explicit optima for exponential cases suggest simple implementation rules when service times are memoryless.

Load-bearing premise

The analysis restricts attention to stationary deterministic policies in which waiting times depend deterministically on instantaneous AoI and the cutoff is fixed across all uploads.

What would settle it

An explicit counterexample policy that achieves strictly lower long-term average AoI than the derived threshold policy for the same service time distribution would falsify the optimality result.

Figures

Figures reproduced from arXiv: 1907.05408 by Ahmed Arafa, H. Vincent Poor, Roy D. Yates.

Figure 1
Figure 1. Figure 1: A scheduler decides on when to acquire new measuremen [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: AoI evolution example in the ith epoch. Red lines denote preemptions and the green line denotes completed service. In this example Ni = 3. at the cloud server denoted as the service time. Service times of different measurements are independent and identically distributed (i.i.d.) according to the distribution of a random variable X. Depending on the application or the task being considered, the server may … view at source ↗
Figure 3
Figure 3. Figure 3: The optimal waiting policy versus time. We show two ex [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Optimal AoI and cutoff values versus c for exponential service times. The vertical line denotes the critical value of c = √ 2, after which the zero-wait policy is optimal. 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 1 1.5 2 2.5 3 3.5 4 4.5 5 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparing the optimal policy to other bench marks ver [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
read the original abstract

The notion of timely status updating is investigated in the context of cloud computing. Measurements of a time-varying process of interest are acquired by a sensor node, and uploaded to a cloud server to undergo some required computations. These computations consume random amounts of service time that are independent and identically distributed across different uploads. After the computations are done, the results are delivered to a monitor, constituting an update. The goal is to keep the monitor continuously fed with fresh updates over time, which is assessed by an age-of-information (AoI) metric. A scheduler is employed to optimize the measurement acquisition times. Following an update, an idle waiting period may be imposed by the scheduler before acquiring a new measurement. The scheduler also has the capability to preempt a measurement in progress if its service time grows above a certain cutoff time, and upload a fresher measurement in its place. Focusing on stationary deterministic policies, in which waiting times are deterministic functions of the instantaneous AoI and the cutoff time is fixed for all uploads, it is shown that the optimal waiting policy that minimizes the long term average AoI has a threshold structure, in which a new measurement is uploaded following an update only if the AoI grows above a certain threshold that is a function of the service time distribution and the cutoff time. The optimal cutoff is then found for standard and shifted exponential service times. While it has been previously reported that waiting before updating can be beneficial for AoI, it is shown in this work that preemption of late updates can be even more beneficial.

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 manuscript analyzes Age-of-Information (AoI) minimization for a cloud computing system in which sensor measurements undergo random i.i.d. service times at the server before delivery. Restricting attention to the class of stationary deterministic policies (waiting time is a deterministic function of instantaneous AoI; preemption cutoff is fixed across uploads), it derives that the AoI-optimal waiting rule has a threshold structure whose value depends on the service-time distribution and the cutoff. It then optimizes the cutoff explicitly for standard and shifted exponential service times and concludes that preemption can be more beneficial than waiting alone.

Significance. If the derivations hold, the work supplies an explicit structural result and closed-form cutoffs for common service distributions inside a clearly delimited policy class. This strengthens the AoI literature on preemption versus waiting and supplies a concrete, implementable scheduler rule for systems with random computation times.

major comments (2)
  1. [Abstract / §3] Abstract and §3 (policy class definition): the central optimality claim is stated only inside the class of stationary deterministic policies; the manuscript should explicitly note that the threshold result does not extend to randomized or non-stationary policies without additional argument, as this scope limitation is load-bearing for the optimality statement.
  2. [Abstract] The claim that preemption 'can be even more beneficial' than waiting (Abstract) is supported only by the optimized cutoffs for exponential families; a direct numerical comparison of the resulting long-run average AoI against the best non-preemptive threshold policy (same service distributions) is needed to make the relative benefit quantitative rather than qualitative.
minor comments (2)
  1. Notation for the cutoff time and the threshold function should be introduced once with a single symbol and used consistently; currently the abstract and body appear to reuse similar symbols without cross-reference.
  2. The service-time distributions for which the optimal cutoff is derived (standard and shifted exponential) should be stated with their exact parameterizations (rate, shift value) in the statement of the main theorem.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive suggestions. We address each major comment below and have revised the manuscript to strengthen clarity and evidence.

read point-by-point responses

  1. Referee: [Abstract / §3] Abstract and §3 (policy class definition): the central optimality claim is stated only inside the class of stationary deterministic policies; the manuscript should explicitly note that the threshold result does not extend to randomized or non-stationary policies without additional argument, as this scope limitation is load-bearing for the optimality statement.

    Authors: We agree that the threshold optimality result is derived strictly within the class of stationary deterministic policies. We will revise the abstract and Section 3 to explicitly state this scope and note that extension to randomized or non-stationary policies would require additional arguments. revision: yes

  2. Referee: [Abstract] The claim that preemption 'can be even more beneficial' than waiting (Abstract) is supported only by the optimized cutoffs for exponential families; a direct numerical comparison of the resulting long-run average AoI against the best non-preemptive threshold policy (same service distributions) is needed to make the relative benefit quantitative rather than qualitative.

    Authors: We will add explicit numerical comparisons of the long-run average AoI achieved by the optimized preemptive policies versus the best non-preemptive threshold policies, using the same exponential and shifted-exponential service distributions. These results will be included in Section 5 to quantify the relative benefit. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation self-contained within stated policy class

full rationale

The paper explicitly limits scope to stationary deterministic policies (waiting times as deterministic functions of instantaneous AoI, fixed cutoff) and derives that the AoI-minimizing policy has a threshold structure, then optimizes the cutoff for exponential and shifted-exponential service times. No equations reduce a claimed optimum to a fitted parameter by construction, no self-citation is invoked as a uniqueness theorem or load-bearing premise, and no ansatz is smuggled via prior work. The result is obtained by direct optimization over the model, making the derivation independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on i.i.d. service times and the deliberate restriction to stationary deterministic policies; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • domain assumption Service times are independent and identically distributed across different uploads
    Stated directly in the model description.
  • ad hoc to paper Analysis is restricted to stationary deterministic policies with deterministic waiting functions of instantaneous AoI and a fixed cutoff
    Explicitly declared focus of the paper.

pith-pipeline@v0.9.0 · 5812 in / 1299 out tokens · 52831 ms · 2026-05-24T22:44:54.844128+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

32 extracted references · 32 canonical work pages · 7 internal anchors

  1. [1]

    S. K. Kaul, R. D. Y ates, and M. Gruteser. Real-time status : How often should one update? In Proc. IEEE Infocom , March 2012

    work page 2012

  2. [2]

    C. Kam, S. Kompella, and A. Ephremides. Age of informatio n under random updates. In Proc. IEEE ISIT , July 2013

    work page 2013

  3. [3]

    Y . Sun, E. Uysal-Biyikoglu, R. D. Y ates, C. E. Koksal, and N. B. Shroff. Update or wait: How to keep your data fresh. IEEE Trans. Inf. Theory , 63(11):7492–7508, November 2017

    work page 2017

  4. [4]

    Talak, S

    R. Talak, S. Karaman, and E. Modiano. Optimizing informa tion freshness in wireless networks under general interference constraints. In Proc. MobiHoc, June 2018

    work page 2018

  5. [5]

    Zhou and W

    B. Zhou and W. Saad. Optimal sampling and updating for min imizing age of information in the internet of things. In Proc. IEEE Globecom , December 2018

    work page 2018

  6. [6]

    Zhang, A

    M. Zhang, A. Arafa, J. Huang, and H. V . Poor. How to price fr esh data. In Proc. WiOpt, June 2019

    work page 2019

  7. [7]

    Bastopcu and S

    M. Bastopcu and S. Ulukus. Minimizing age of information with soft updates. J. Commun. Netw. , 2019. To appear

    work page 2019

  8. [8]

    Buyukates, A

    B. Buyukates, A. Soysal, and S. Ulukus. Age of informatio n in multihop multicast networks. J. Commun. Netw. , 2019. To appear

    work page 2019

  9. [9]

    X. Wu, J. Y ang, and J. Wu. Optimal status update for age of i nformation minimization with an energy harvesting source. IEEE Trans. Green Commun. Netw., 2(1):193–204, March 2018

    work page 2018

  10. [10]

    Age-Minimal Transmission for Energy Harvesting Sensors with Finite Batteries: Online Policies

    A. Arafa, J. Y ang, S. Ulukus, and H. V . Poor. Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies. Available Online: arXiv:1806.07271

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    B. T. Bacinoglu, Y . Sun, E. Uysal-Biyikoglu, and V . Mutl u. Achieving the age-energy tradeoff with a finite-battery energy harves ting source. In Proc. IEEE ISIT , June 2018

    work page 2018

  12. [12]

    T. Z. Ornee and Y . Sun. Sampling for remote estimation th rough queues: Age of information and beyond. In Proc. WiOpt, June 2019

    work page 2019

  13. [13]

    R. D. Y ates, E. Najm, E. Soljanin, and J. Zhong. Timely up dates over an erasure channel. In Proc. IEEE ISIT , June 2017

    work page 2017

  14. [14]

    Arafa, K

    A. Arafa, K. Banawan, K. Seddik, and H. V . Poor. On timely channel coding with hybrid ARQ. Available Online: arXiv:1905.0323 8

    work page arXiv 1905

  15. [15]

    S. K. Kaul, R. D. Y ates, and M. Gruteser. Status updates t hrough queues. In Proc. CISS, March 2012

    work page 2012

  16. [16]

    Costa, M

    M. Costa, M. Codreanu, and A. Ephremides. On the age of in formation in status update systems with packet management. IEEE Trans. Inf. Theory, 62(4):1897–1910, April 2016

    work page 1910

  17. [17]

    Chen and L

    K. Chen and L. Huang. Age-of-information in the presenc e of error. In Proc. IEEE ISIT , June 2016

    work page 2016

  18. [18]

    R. D. Y ates and S. K. Kaul. The age of information: Real-t ime status updating by multiple sources. IEEE Trans. Inf. Theory , 65(3):1807– 1827, March 2019

    work page 2019

  19. [19]

    Najm and E

    E. Najm and E. Telatar. Status updates in a multi-stream M/G/1/1 preemptive queue. In Proc. IEEE Infocom , April 2018

    work page 2018

  20. [20]

    Age of Information in G/G/1/1 Systems: Age Expressions, Bounds, Special Cases, and Optimization

    A. Soysal and S. Ulukus. Age of information in G/G/1/1 sy stems: Age expressions, bounds, special cases, and optimization. Ava ilable Online: arXiv:1905.13743

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  21. [21]

    Farazi, A

    S. Farazi, A. G. Klein, and D. R. Brown III. Age of informa tion in energy harvesting status update systems: When to preempt in service? In Proc. IEEE ISIT , June 2018

    work page 2018

  22. [22]

    Controlling Packet Drops to Improve Freshness of information

    V . Kavitha abd E. Altman and I. Saha. Controlling packet drops to improve freshness of information. Available Online: arXiv :1807.09325

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    B. Wang, S. Feng, and J. Y ang. When to preempt? age of info rmation minimization under link capacity constraint. J. Commun. Netw. , 2019. To appear

    work page 2019

  24. [24]

    C. Xu, H. H. Y ang, X. Wang, and T. Q. S. Quek. On peak age of information in data preprocessing enabled IoT networks. In Proc. IEEE WCNC, April 2019

    work page 2019

  25. [25]

    Age-of-Information for Computation-Intensive Messages in Mobile Edge Computing

    Q. Kuang, J. Gong, X. Chen, and X. Ma. Age-of-informatio n for computation-intensive messages in mobile edge computing. Available Online: arXiv:1901.01854

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  26. [26]

    J. Gong, Q. Kuang, X. Chen, and X. Ma. Reducing age-of-in formation for computation-intensive messages via packet replacemen t. Available Online: arXiv:1901.04654

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  27. [27]

    P . Zou, O. Ozel, and S. Subramaniam. Trading off computa - tion with transmission in status update systems. Available Online: arXiv:1907.00928

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  28. [28]

    X. Song, X. Qin, Y . Tao, B. Liu, and P . Zhang. Age based tas k scheduling and computation offloading in mobile-edge compu ting sys- tems. Available Online: arXiv:1905.11570

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  29. [29]

    R. D. Y ates, M. Tavan, Y . Hu, and D. Raychaudhuri. Timely cloud gaming. In Proc. IEEE Infocom , May 2017

    work page 2017

  30. [30]

    Dinkelbach

    W. Dinkelbach. On nonlinear fractional programming. Management Science, 13(7):492–498, 1967

    work page 1967

  31. [31]

    S. P . Boyd and L. V andenberghe. Convex Optimization . Cambridge University Press, 2004

    work page 2004

  32. [32]

    D. G. Luenberger. Optimization by V ector Space Methods . John Wiley & Sons, 1997

    work page 1997