pith. sign in

arxiv: 1907.00928 · v1 · pith:OLRK7DZLnew · submitted 2019-07-01 · 💻 cs.IT · cs.NI· math.IT

Trading Off Computation with Transmission in Status Update Systems

Peng Zou , Omur Ozel , Suresh Subramaniam This is my paper

Pith reviewed 2026-05-25 11:30 UTC · model grok-4.3

classification 💻 cs.IT cs.NImath.IT
keywords age of informationstatus updatestandem queuesedge computingcomputation-transmission tradeoffstationary distributionpeak age of informationM/GI/1/1 queue
0
0 comments X

The pith

Tandem queues with dependent service times yield closed-form expressions for average age of information and peak age of information.

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

The paper models an edge computing setup where status updates undergo pre-processing at a source before transmission to a server, capturing the tradeoff via two queues whose mean service times are linked by a deterministic monotonic function. The first queue is M/GI/1/1 and the second is GI/M/1/2*, both non-preemptive, with stationary distribution analysis performed to derive explicit formulas for the long-run average AoI and average peak AoI. A sympathetic reader cares because these formulas quantify how allocating effort between computation and transmission affects information freshness in systems that must deliver timely updates. The analysis shows that the tandem structure and the service-time dependence together produce a concrete tradeoff surface between the two AoI metrics.

Core claim

For the tandem system consisting of an M/GI/1/1 queue followed by a GI/M/1/2* queue whose mean service times are related by a deterministic monotonic function, stationary distribution analysis produces closed-form expressions for both the average age of information and the average peak age of information; numerical evaluation of these expressions confirms the existence of a tradeoff generated by the tandem structure and the service-time dependence.

What carries the argument

The tandem non-preemptive queue pair (M/GI/1/1 followed by GI/M/1/2*) whose mean service times are linked by a deterministic monotonic function, together with the stationary distribution analysis that converts this linkage into explicit AoI formulas.

If this is right

  • The average AoI and peak AoI can each be written as explicit functions of the monotonic dependence parameter.
  • Numerical minimization of either metric over the dependence parameter identifies an optimal operating point between computation and transmission.
  • The tandem structure causes average AoI and peak AoI to respond differently to changes in the dependence parameter.
  • The closed forms remain valid for any monotonic function relating the two mean service times.

Where Pith is reading between the lines

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

  • The same stationary-distribution technique could be applied to multi-hop status-update paths that also contain computation stages.
  • Relaxing the deterministic monotonic dependence to a stochastic one would require a different analysis but could still be compared against the closed forms derived here.
  • The tradeoff surface obtained from the expressions supplies a benchmark for heuristic policies that adapt computation effort on the fly.

Load-bearing premise

The mean service times of the computation queue and the transmission queue are connected by a deterministic monotonic function.

What would settle it

Simulations of the two-queue system that use a monotonic deterministic mapping between the two mean service times produce average AoI values that deviate from the derived closed-form expressions.

Figures

Figures reproduced from arXiv: 1907.00928 by Omur Ozel, Peng Zou, Suresh Subramaniam.

Figure 1
Figure 1. Figure 1: System model with status update packets arriving to a single server transmission queue from the output of a computation server queue in tandem. [27], [28] consider AoI analysis with tandem computing and communication queues. In this paper, we consider a status update system composed of tandem queues where a computation-type first queue determines status update packets to be sent to a remote monitoring rece… view at source ↗
Figure 2
Figure 2. Figure 2: AoI evolution for the equivalent tandem queue model with M/GI/1/1 following GI/M/1/2*. the service time for packet i in the second queue. The instantaneous AoI is the difference of current time and the time stamp of the packet at the receiver: ∆(t) = t − u(t) (2) where u(t) is the time stamp of the latest packet at the receiver at time t. We express u(t) = ti ∗ where i ∗ = max{i : t ′ i ≤ t}. We provide a … view at source ↗
Figure 3
Figure 3. Figure 3: Average AoI with respect to E[P] for fixed λ = 0.4, B0 = 15 and α = 0.1. transmission time is expected to be bounded due to diminishing returns. Its smoothness makes it suitable for use as an approximation for many potential non-smooth variations of it. We let the expected processing time to be selected from the interval Pmin ≤ E[P] ≤ Pmax. We take Pmin = 1 and Pmax = 10 in the rest. We use Gamma distribut… view at source ↗
Figure 5
Figure 5. Figure 5: Average and average peak AoI with respect to k for fixed λ = 0.4, B0 = 15 and α = 0.1. 26.7 26.8 26.9 27 27.1 27.2 27.3 27.4 27.5 22.6 22.8 23 23.2 23.4 23.6 23.8 k=6 k=10 k=20 [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: , we plot the optimal tradeoff obtained by solving the weighted optimization in (18) for differing service time variances. In particular, for each k determining the service time variance, we solve (18) for all possible ω1 and ω2 and plot all possible operating points as tuples of average AoI and average peak AoI. This characterizes the optimal tradeoff between average AoI and average peak AoI. We observe t… view at source ↗
Figure 7
Figure 7. Figure 7: Optimal average AoI and optimal E[P] with respect to α for various k and fixed λ = 0.4 and B0 = 15. mission queue with arrivals coming from the computa￾tion queue. Moreover, there is a functional dependence between the mean service times of the first and the second queues. We obtain closed form expressions for average peak AoI and average AoI in this system. Our expressions provide explicit relations among… view at source ↗
read the original abstract

This paper is motivated by emerging edge computing applications in which generated data are pre-processed at the source and then transmitted to an edge server. In such a scenario, there is typically a tradeoff between the amount of pre-processing and the amount of data to be transmitted. We model such a system by considering two non-preemptive queues in tandem whose service times are independent over time but the transmission service time is dependent on the computation service time in mean value. The first queue is in M/GI/1/1 form with a single server, memoryless exponential arrivals, general independent service and no extra buffer to save incoming status update packets. The second queue is in GI/M/1/2* form with a single server receiving packets from the first queue, memoryless service and a single data buffer to save incoming packets. Additionally, mean service times of the first and second queues are dependent through a deterministic monotonic function. We perform stationary distribution analysis in this system and obtain closed form expressions for average age of information (AoI) and average peak AoI. Our numerical results illustrate the analytical findings and highlight the tradeoff between average AoI and average peak AoI generated by the tandem nature of the queueing system with dependent service times.

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

0 major / 3 minor

Summary. The paper models status update systems in edge computing via a tandem queue: an M/GI/1/1 computation queue followed by a GI/M/1/2* transmission queue, with mean service times linked by a deterministic monotonic function to capture the computation-transmission tradeoff. Stationary distribution analysis yields closed-form expressions for average AoI and average peak AoI; numerical results illustrate the resulting tradeoff.

Significance. If the derivations hold, the closed-form AoI expressions constitute a useful analytical contribution to the AoI literature by extending standard tandem-queue models to include mean-dependent service times without introducing state-dependent rates. This enables direct optimization of the tradeoff parameter rather than relying exclusively on simulation.

minor comments (3)
  1. [§II] §II (Model): the precise definition of the monotonic function relating the two mean service times and the range of admissible parameters should be stated explicitly, as it parameterizes all subsequent expressions.
  2. The notation 'GI/M/1/2*' for the second queue is non-standard; a footnote or sentence clarifying the buffer semantics and the '*' would improve readability.
  3. [Numerical Results] Numerical results: the specific functional forms chosen for the monotonic link (e.g., linear, exponential) and the numerical values of the free parameters should be listed in a table for reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our contribution. The recommendation for minor revision is noted. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is standard stationary analysis

full rationale

The paper models a tandem queue (M/GI/1/1 followed by GI/M/1/2*) with independent realizations but means linked by a fixed monotonic function, then applies standard balance-equation methods to obtain closed-form AoI expressions. This is a direct, self-contained queueing-theoretic derivation with no reduction of outputs to fitted inputs, no self-definitional steps, and no load-bearing self-citations. The monotonic link parameterizes the tradeoff but does not create state-dependent rates that would invalidate the stationary analysis or force the result by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The model rests on standard queueing assumptions plus the specific dependence between service means; full paper would likely introduce the explicit form of the monotonic function as a modeling choice.

free parameters (1)
  • monotonic function relating mean service times
    Deterministic monotonic mapping between computation and transmission mean service times is introduced to capture the tradeoff; its specific form is a modeling parameter.
axioms (1)
  • domain assumption Stationary distribution exists for the described tandem non-preemptive queues
    Invoked to obtain closed-form AoI expressions.

pith-pipeline@v0.9.0 · 5750 in / 1206 out tokens · 25616 ms · 2026-05-25T11:30:46.809834+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Timely Cloud Computing: Preemption and Waiting

    cs.IT 2019-07 unverdicted novelty 6.0

    In cloud status updates with i.i.d. random service times, the optimal deterministic policy minimizing long-run average AoI uses a threshold on current age to decide when to upload and a fixed cutoff to preempt long co...

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · cited by 1 Pith paper · 12 internal anchors

  1. [1]

    Kaul, R.D

    S.K. Kaul, R.D. Y ates, and M. Gruteser. Status updates th rough queues. In Information Sciences and Systems (CISS), 2012 46th Annual Conference on , pages 1–6. IEEE, 2012

    work page 2012

  2. [2]

    S. Kaul, R. Y ates, and M. Gruteser. Real-time status: How often should one update ? In INFOCOM, pages 2731–2735. IEEE, 2012

    work page 2012

  3. [3]

    Costa, M

    M. Costa, M. Codreanu, and A. Ephremides. On the age of information in status update systems with packet managemen t. IEEE Transactions on Information Theory , 62(4):1897–1910, 2016

    work page 1910

  4. [4]

    C. Kam, S. Kompella, G.D. Nguyen, J.E. Wieselthier, and A. Ephremides. On the age of information with packet deadlin es. IEEE Transactions on Information Theory , 2018

    work page 2018

  5. [5]

    Inoue, H

    Y . Inoue, H. Masuyama, T. Takine, and T. Tanaka. A general formula for the stationary distribution of the age of inform ation and its application to single-server queues. arXiv preprint arXiv:1804.06139, 2018

    work page arXiv 2018

  6. [6]

    Najm and R

    E. Najm and R. Nasser. Age of information: The gamma awak- ening. In Information Theory (ISIT), 2016 IEEE International Symposium on , pages 2574–2578. Ieee, 2016

    work page 2016

  7. [7]

    E. Najm, R. Y ates, and E. Soljanin. Status updates throug h M/G/1/1 queues with HARQ. In IEEE ISIT , 2017

    work page 2017

  8. [8]

    Baknina, O

    A. Baknina, O. Ozel, J. Y ang, S. Ulukus, and A. Y ener. Send ing information through status updates. In IEEE ISIT , 2018

    work page 2018

  9. [9]

    B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu. Age of information under energy replenishment constraints. In USCD ITA, February 2015

    work page 2015

  10. [10]

    R. Y ates. Lazy is timely: Status updates by an energy har vesting source. In IEEE ISIT , June 2015

    work page 2015

  11. [11]

    X. Wu, J. Y ang, and J. Wu. Optimal status update for age of information minimization with an energy harvesting source . IEEE Trans. on Green Communications and Networking , 2(1), March 2018

    work page 2018

  12. [12]

    Arafa and S

    A. Arafa and S. Ulukus. Age-minimal transmission in ene rgy harvesting two-hop networks. In IEEE Globecom , December 2017

    work page 2017

  13. [13]

    Bacinoglu and E

    B.T. Bacinoglu and E. Uysal-Biyikoglu. Scheduling sta tus updates to minimize age of information with an energy harves ting sensor. In IEEE ISIT , pages 1122–1126. IEEE, 2017

    work page 2017

  14. [14]

    Farazi, A.G

    S. Farazi, A.G. Klein, and D.R. Brown. Average age of inf orma- tion for status update systems with an energy harvesting ser ver. In IEEE INFOCOM WORKSHPS , pages 112–117, 2018

    work page 2018

  15. [15]

    Bacinoglu, Y

    B.T. Bacinoglu, Y . Sun, E. Uysal-Bivikoglu, and V . Mutl u. Achieving the age-energy tradeoff with a finite-battery ene rgy harvesting source. In IEEE ISIT , pages 876–880. IEEE, 2018

    work page 2018

  16. [16]

    Age of Information Minimization for an Energy Harvesting Source with Updating Erasures: With and Without Feedback

    S. Feng and J. Y ang. Age of information minimization for an energy harvesting source with updating erasures: With an d without feedback. arXiv preprint arXiv:1808.05141 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  17. [17]

    Using Erasure Feedback for Online Timely Updating with an Energy Harvesting Sensor

    Ahmed Arafa, Jing Y ang, Sennur Ulukus, and H Vincent Poo r. Using erasure feedback for online timely updating with an en ergy harvesting sensor. arXiv preprint arXiv:1901.08577 , 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  18. [18]

    A. M. Bedewy, Y . Sun, and N. B. Shroff. Age-optimal information updates in multihop networks. Available at arXiv:1701.05711, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  19. [19]

    Talak, S

    R. Talak, S. Karaman, and E. Modiano. Minimizing age-of - information in multi-hop wireless networks. In Communication, Control, and Computing (Allerton), 2017 55th Annual Allert on Conference on , pages 486–493. IEEE, 2017

    work page 2017

  20. [20]

    R.D. Y ates. The age of information in networks: Moments , distributions, and sampling. arXiv preprint arXiv:1806.03487 , 2018

    work page arXiv 2018

  21. [21]

    R.D. Y ates. Status updates through networks of paralle l servers. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 2281–2285. IEEE, 2018

    work page 2018

  22. [22]

    The Age of Updates in a Simple Relay Network

    A. Maatouk, M. Assaad, and A. Ephremides. The age of upda tes in a simple relay network. arXiv preprint arXiv:1805.11720 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  23. [23]

    Age of Information and Throughput in a Shared Access Network with Heterogeneous Traffic

    A. Kosta, N. Pappas, A. Ephremides, and V . Angelakis. Ag e of information and throughput in a shared access network wit h heterogeneous traffic. arXiv preprint arXiv:1806.08776 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  24. [24]

    Kadota, A

    I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E . Modi- ano. Scheduling policies for minimizing age of information in broadcast wireless networks. IEEE/ACM Transactions on Networking, (6):2637–2650, 2018

    work page 2018

  25. [25]

    Adaptive Coding for Information Freshness in a Two-user Broadcast Erasure Channel

    Songtao Feng and Jing Y ang. Adaptive coding for informa tion freshness in a two-user broadcast erasure channel. arXiv preprint arXiv:1905.00521, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  26. [26]

    Joint Information Freshness and Completion Time Optimization for Vehicular Networks

    A. Alabbasi and V . Aggarwal. Joint information freshne ss and completion time optimization for vehicular networks. CoRR, abs/1811.12924, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  27. [27]

    J. Gong, Q. Kuang, X. Chen, and X. Ma. Reducing age- of-information for computation-intensive messages via pa cket replacement. CoRR, abs/1901.04654, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  28. [28]

    C. Xu, H. H. Y ang, X. Wang, and T.Q.S Quek. On peak age of information in data preprocessing enabled IoT networks. arXiv preprint arXiv:1901.09376 , 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  29. [29]

    P . Zou, O. Ozel, and S. Subramaniam. On the benefits of wai ting in status update systems. In IEEE INFOCOM AoI WORKSHOP , April 2019

    work page 2019

  30. [30]

    P . Zou, O. Ozel, and S. Subramaniam. Waiting before serv ing: A companion to packet management in status update systems. arXiv preprint arXiv:1901.02873 , 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  31. [31]

    P . Zou, O. Ozel, and S. Subramaniam. Relative age of in- formation: A new metric for status update systems. preprint arXiv:1901.05428, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  32. [32]

    Can Determinacy Minimize Age of Information?

    R. Talak, S. Karaman, and E. Modiano. Can determinacy minimize age of information? preprint arXiv:1810.04371 , 2018. 7

    work page internal anchor Pith review Pith/arXiv arXiv 2018