On the Role of Early-Termination for Age of Information in Tree-Based Random Access Protocols

Andrea Munari; Cedomir Stefanovic

REVIEW 3 major objections 4 minor 16 references

On the Role of Early-Termination for Age of Information in Tree-Based Random Access Protocols

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper gives the first analytical formula for the average Age of Information of the Capetanakis tree-based random access protocol with gated access, and shows that truncating collision resolution after $L_m$ slots can improve freshness.

desk verdict First analytic AoI for tree random access under exogenous traffic — solid and novel, with one conditional approximation that deserves a direct test before reliance. read the letter →

arxiv 2506.04793 v1 pith:JOF5MJCL submitted 2025-06-05 cs.IT cs.NImath.IT

Andrea Munari , Cedomir Stefanovic This is my paper

classification cs.ITcs.NImath.IT MSC 94A0560J10

keywords ageofinformationtree-basedrandomaccessCapetanakisalgorithmearlyterminationcollisionresolutionexogenoustrafficMarkovchainfreshness-latencytrade-off

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper aims to establish the first analytical characterization of average Age of Information (AoI) for the Capetanakis tree-based random-access protocol with gated access, under exogenous traffic where each of $U$ terminals independently generates a packet in a slot with probability $\rho$. The motivation is practical: IoT devices send sporadic, time-stamped updates, so the freshness of information at a receiver matters as much as throughput. If the formulas are correct, protocol designers can compute the average AoI directly for any finite population, generation rate, and early-termination bound $L_m$, and can choose $L_m$ to minimize staleness instead of relying on simulation. The analysis also uncovers a reliability-timeliness trade-off: truncating a collision-resolution interval after $L_m$ slots drops stale packets, and this can improve freshness by roughly 30% at high load, while at low load full resolution is better. The key object is the inter-refresh time $Y$ and the reset age $Z$, whose joint statistics are obtained from a Markov chain on collision-resolution-interval durations.

What carries the argument

The central object is a Markov chain on the duration of contention resolution intervals (CRIs). After a CRI of $\ell$ slots, each of the $U$ terminals has generated at least one packet with probability $\Gamma_\ell = 1-(1-\rho)^\ell$, so the number of contenders in the next CRI is binomial, and the next CRI length follows from conditional PMF (4). The per-CRI length PMF and the per-user decoding-delay PMF are obtained from probability-generating-function recursions, Eqs. (1) and (2), for the binary fair-splitting tree process. A first-step analysis then converts the Markov recurrence into two linear systems, Eqs. (10) and (11), whose unknowns are $E[Y\,|\,L'_1=\ell'_1]$ and $E[Y^2\,|\,L'_1=\ell'_1]$; the reset value $Z=X+D$ is handled by the geometric PMF (13) for $X$ and the approximated conditional distribution (14) for $D$. These ingredients are assembled in the geometric AoI identity, Eq. (6).

What would settle it

Run Monte Carlo simulations for population sizes outside $U=100$ (for instance $U=10$ and $U=1000$) and for extreme generation rates, and compare $\Delta$ from Eqs. (6)-(14) with the simulated average; if the gap grows beyond the few-percent level reported in Fig. 3, the approximation $E[D\,|\,L'_0,L'_1]\simeq E[D\,|\,L'_0]$ has failed. A sharper test is to compute the exact joint law of $(D,Y)$ by direct enumeration of the tree-splitting process for moderate $U$ and compare the resulting $E[ZY]$ with the value obtained under the approximation.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that for a finite population of $U$ terminals with one-packet buffers and pre-emption in waiting, the stationary average AoI of a reference user is given by $\Delta = (E[ZY] + E[Y^2]/2)/E[Y]$, where $Y$ is the number of slots between two successive successful deliveries and $Z$ is the age value at which the AoI resets. It derives the conditional moments of $Y$ through first-step recursions, Eqs. (10)-(11), and $E[ZY]$ through the joint distribution of two consecutive CRI durations, Eq. (9), after writing $Z = X + D$ with $X$ the packet's waiting time until the end of its generating CRI and $D$ the decoding delay in the next CRI. For $D$, the paper introduces and numerically validates the approximation $E[D\,|\,L'_0=\ell'_0, L'_1=\ell'_1] \simeq E[D\,|\,L'_0=\ell'_0]$, because an exact conditioning on both intervals would require interdependencies not captured by standard tree recursions. The same framework covers plain CTM (recovered as $L_m\to\infty$) and the early-termination variant, and it is validated by Monte Carlo simulation for $U=100$ across a wide range of aggregate generation rates and thresholds $L_m$. The paper positions this as the first analytical average-AoI result for tree-based random access under exogenous traffic.

Load-bearing premise

The formula is only as accurate as the approximation that, after a collision-resolution interval of a given length, the delay until the next successful delivery depends almost only on that previous interval's length and can be treated as the simple sum of interval durations, rather than on the full joint history of the two intervals.

Editorial extensions

If this is right

Average AoI becomes a computable protocol metric for tree-based random access, so the early-termination threshold $L_m$ can be optimized per load without Monte Carlo simulation.
Plain CTM is recovered as the $L_m\to\infty$ limit, so one unified formula covers both complete and truncated collision resolution.
At high aggregate generation rates, an aggressive early termination (e.g., $L_m=2$) can reduce the normalized average AoI by about 30% compared with resolving all collisions, because stale packets are dropped instead of delivered.
At low rates, early termination degrades AoI (more than 15% worse for $L_m=2$), indicating that full collision resolution matters under sparse traffic.
The Markovian structure carries over to other tree/stack algorithms once their per-CRI and per-user decoding delay statistics are known.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the recursions already produce $E[Y^2]$, the same machinery could be extended to peak-AoI or to the full distribution of AoI, not just its average.
The optimal-$L_m$ curve in Fig. 4(b) suggests a simple design rule: keep full resolution while the load is near or below the throughput peak, then shrink $L_m$ as load rises; this is the paper's implicit tuning guideline.
The approximation for the decoding delay may become exact in heavy-traffic regimes where CRIs are almost always truncated at $L_m$, which would allow a fully closed-form asymptotic AoI.
For finite $U$, the stationary distribution of CRI durations could be replaced by the exact joint law of $(L_0,L_1)$ to remove the only approximation, at the cost of solving larger systems; this would be a natural check of robustness.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper gives the first analytic average-AoI characterization for Capetanakis tree-based random access with gated access under exogenous traffic, plus an early-termination variant. The Markovian first-step analysis in Sec. IV is careful, and the simulation match for U=100 across the plotted load and Lm values is convincing. If you work on AoI or random access, this is worth reading.

What's genuinely new is the AoI recursion itself. Earlier work on tree algorithms with AoI assumed generate-at-will; here the chance that a user has a packet depends on the previous CRI length, and that's exactly the coupling the recursion captures. The early-termination idea — truncated resolution that drops stale packets to improve freshness — is also new in this context, and the paper turns it into a usable tuning rule for Lm. The authors reuse known PGF recursions from [6] and [7], but the combination into the inter-refresh-time moments and the reset-value calculation is original. Credit is given where it's due.

The soft spot is in Sec. IV-B. The derivation replaces E[D|L'0,L'1] with E[D|L'0] in Eq. (12), and calls it 'extremely tight' by pointing to Fig. 2(b). But Fig. 2(b) validates only the marginal E[D], not the conditional quantity that the factorization actually uses. The final AoI curves in Fig. 3 also match well, which is evidence, but it isn't a direct check of the conditional approximation. Since E[ZY] in Eq. (12) is a product of this conditional expectation with E[Y|L'1], any bias here propagates into the reported AoI. The approximation is plausible — L0 roughly drives the number of contenders in C1 — and the simulation agreement suggests it's harmless in the tested regime, but it's under-validated. A referee should ask for a direct simulation of the conditional E[D|L'0,L'1] versus the approximation, or an error bound.

Minor editorial issue: Sec. II has a duplicated paragraph about Gallager's counters, a copy-paste artifact.

Who is this for? People working on IoT random access, AoI analysis, or collision resolution protocols. It doesn't reorganize the field, but it fills a specific gap and provides practical protocol design guidance. I'd cite it.

Recommendation: it deserves peer review. Send it out, ask for a direct validation of the conditional approximation and a fix for the duplicated paragraph. The core derivation is sound and novel; the request is a moderate revision, not a rejection.

Referee Report

3 major / 4 minor

Summary. The paper studies the average Age of Information for a finite population of U users running the Capetanakis tree-based random access protocol with gated access under exogenous Bernoulli traffic. The authors derive a Markovian model for the contention resolution interval (CRI) durations and use it to compute the first and second moments of the AoI inter-refresh time via first-step recursions (Eqs. (10)-(11)), together with an expression for the reset value E[ZY] (Eq. (12)) that relies on two stated approximations introduced in Sec. IV-B: Y is approximated by the sum of CRI durations, and E[D|L0,L1] is approximated by E[D|L0] in Eq. (14). They also introduce early termination at Lm slots, study its effect on delivery rate, delay, and AoI, and provide an optimal Lm selection. Numerical results are given for U=100 users across a range of aggregate generation rates.

Significance. If the analytical characterization is correct, it provides the first computable average-AoI formula for a classical tree-based random access protocol under exogenous traffic, a setting that is relevant for IoT and that previous work had only treated in the generate-at-will case. The paper is strong in that the Markovian first-step analysis is careful, the conditional distributions are derived explicitly rather than fitted, and the authors validate their expressions with independent Monte Carlo simulation. The practical takeaway on early termination, namely that truncating long CRIs can reduce AoI under high load despite lowering delivery rate, is interesting and well motivated. However, the central claim rests on two approximations whose individual accuracy is not directly demonstrated; the current validation is confined to one population size and to the final AoI metric, so the generality of the reported formula is not fully established.

major comments (3)

[Sec. IV-B, Eq. (12) and Eq. (14)] The approximation E[D|L0=ℓ0, L1=ℓ1] ≃ E[D|L0=ℓ0] is load-bearing for the computation of E[ZY] in Eq. (12). The factorization after conditioning on (L0, L1) is exact, but replacing the conditional decoding delay by a quantity that marginalizes over M|L0 discards any dependence of D on L1 beyond what is captured by L0. Such dependence is plausible, as a longer C1 duration may reflect a heavier collision subtree and hence a later decoding slot. The paper's Fig. 2(b) validates only the marginal E[D], and Fig. 3 validates only the final average AoI for U=100; neither isolates E[ZY] or the conditional approximation. Please add a direct numerical comparison of the approximate conditional expectation E[D|L0=ℓ0] against simulated E[D|L0=ℓ0, L1=ℓ1] (or, equivalently, of the full term E[ZY] computed via the approximation versus simulation), for several (ℓ0, ℓ1, ρ) combinations and for more than one population size. Without such a diagnostic, the claimed analytical characterization is not established outside the plotted regime.
[Sec. IV-B, Y approximation and Eqs. (10)-(11)] The replacement Y ≃ Σ_{i=1}^K L′_i affects both E[Y] and E[Y^2] through the recursions in Eqs. (10)-(11), and therefore both numerator terms in Eq. (6). The paper states that the approximation is tight and that this is verified in Sec. V, but Fig. 3 only shows the final average AoI. Since errors in E[ZY] and E[Y^2] could compensate, agreement in Δ does not demonstrate that the individual moments are accurate. Please report simulated and analytical values of E[Y], E[Y^2], and E[ZY] separately (or provide the mean and variance of the approximation error) for the configurations in Fig. 3, and ideally for a second population size. This would make the validation of the first-step recursions more direct.
[Sec. V, Fig. 3 and Sec. IV-B] The text states that the approximation E[D|L0,L1] ≃ E[D|L0] 'proves to be extremely tight for all configurations of arrival rate and Lm, as highlighted in Fig. 2(b)', but Fig. 2(b) is generated for U=100 only and shows only the marginal E[D], not the conditional quantity used in Eq. (12). The paper also mentions that other U values were studied but not reported. Since the population size U affects the binomial distributions and the CRI length distribution, it is important to show at least one additional U (e.g., U=10 and U=1000) to support the claim of universal tightness. This is a validation completeness issue rather than a defect in the derivation.

minor comments (4)

[Sec. II] The description of the Gallager counter implementation appears twice, with nearly identical wording, in the same section. Please remove the duplicate paragraph.
[Throughout] There are several typographical errors, including 'probabiltiy', 'oher', 'accomodate', 'singelton', and 'contetion'. One instance of 'CMT-ET' appears in Sec. V and should read 'CTM-ET'.
[Eq. (1)] In Lemma 1, the terms '2u−1' and 'z2' should be typeset as 2^{u-1} and z^2, respectively, to avoid ambiguity.
[Sec. V, Fig. 4(b)] The gray-shaded region in Fig. 4(b) is described as corresponding to Lm=∞ (plain CTM), but the shading is not visible in a monochrome print; please use a distinct pattern or add an annotation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the analytical AoI expressions are derived from protocol recursions and binomial traffic statistics, with no fitted parameters; the two explicit approximations are validated by independent Monte Carlo simulation.

full rationale

The paper's central claim is a computable analytical expression for the average Age of Information under CTM and CTM-ET, given by Eq. (6) together with the recursions in Eqs. (1), (2), (10), (11), and the reset-value calculation in Eqs. (12)-(14). The derivation chain is self-contained: the CRI-duration PGF in Lemma 1 is a standard known result with a proof sketch; the decoding-delay PGF in Lemma 2 is attributed to an external prior work and rearranged for the binary fair-splitting case; Lemma 3 follows directly from Lemma 2. The Markov model for consecutive CRI durations is built from the stated binomial traffic model in Eqs. (3)-(4), and the moments of the inter-refresh time are obtained by standard first-step analysis. No parameter is fitted to simulation data, and no quantity presented as a prediction is actually an input. The two approximations introduced in Sec. IV-B, namely Y approximated by the sum of CRI durations and E[D|L'0,L'1] approximated by E[D|L'0], are explicitly labeled as approximations and are checked against independent Monte Carlo simulations in Figs. 2 and 3. Even if those approximations were imperfect outside the tested regime, approximation error is not circularity. Self-citations [13] and [14] are used only for standard AoI renewal formulas and benchmark computations, not as load-bearing uniqueness or derivation steps. Therefore, no circular step is identified, and the paper is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; model inputs ρ, U, Lm are exogenous. The analysis relies on standard PGF techniques and the Markov property of CRI durations, plus domain assumptions about channel feedback and packet generation. No new physical or algorithmic entities are introduced beyond the early-termination variant of CTM.

assumptions (4)

domain assumption The duration of consecutive contention resolution intervals forms a Markov chain with transition probabilities given by Eq. (4).
Assumed in Sec. IV-A, required for the first-step analysis in (10) and (11). It follows from the protocol when packet generation is i.i.d., but is still a modeling assumption.
domain assumption Each user independently generates a packet in a slot with probability ρ, with preemption in a one-packet buffer.
Exogenous traffic model described in Sec. II; determines Γℓ and the binomial distributions in Eq. (3).
domain assumption Ternary, instantaneous, ideal feedback is available to all users after each slot.
Standard CTM assumption stated in Sec. II; required for the counter-based implementation.
standard math Standard PGF recursions for CRI length and decoding delay from [6] and [7] are correct.
Used in Lemmas 1 and 2 without reproof; these are previously established results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Role of Early-Termination for Age of Information in Tree-Based Random Access Protocols." pith.science (2026). https://pith.science/paper/JOF5MJCL

@misc{pith2026250604793,
  author       = {Pith},
  title        = {Pith review of: On the Role of Early-Termination for Age of Information in Tree-Based Random Access Protocols},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JOF5MJCL}},
  note         = {Machine review of arXiv:2506.04793}
}

read the original abstract

Age of Information (AoI) has emerged as a key metric for assessing data freshness in IoT applications, where a large number of devices report time-stamped updates to a monitor. Such systems often rely on random access protocols based on variations of ALOHA at the link layer, where collision resolution algorithms play a fundamental role to enable reliable delivery of packets. In this context, we provide the first analytical characterization of average AoI for the classical Capetanakis tree-based algorithm with gated access under exogenous traffic, capturing the protocol's dynamics, driven by sporadic packet generation and variable collision resolution times. We also explore a variant with early termination, where contention is truncated after a maximum number of slots even if not all users are resolved. The approach introduces a fundamental trade-off between reliability and timeliness, allowing stale packets to be dropped to improve freshness.

Figures

Figures reproduced from arXiv: 2506.04793 by the authors.

**Figure 2.** (a) packet delivery rate, ps and (b) average delay, E[D], plotted against the aggregate generation rate ρU. For d∈{1, . . . , Lm}, the numerator in (14) reflects the condition on L ′ 0 in terms of the number of contenders M over C1, while the denominator provides the normalization for considering CRIs (and thus decoding) of maximum Lm slots. The distributions in (13) and (14) allow to compute the (approximated) con… view at source ↗

**Figure 4.** (a) minimum normalized average AoI for the optimized CTM-ET, [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[6]

Q-ary collision resolution algorithms in random-access systems with free or blocked channel access,

P. Mathys and P. Flajolet, “Q-ary collision resolution algorithms in random-access systems with free or blocked channel access,” vol. 31, no. 2, pp. 217–243, 1985

work page 1985
[7]

High-throughput random access using successive interference cancellation in a tree algorithm,

Y . Yu and G. B. Giannakis, “High-throughput random access using successive interference cancellation in a tree algorithm,” vol. 53, no. 12, pp. 4628–4639, 2007

work page 2007
[1]

Tree algorithms for packet broadcast channels,

J. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Trans. Inf. Theory, vol. 25, no. 5, pp. 505–515, 1979

work page 1979
[2]

Age of information: An introduction and survey,

R. Yates, Y . Sun, D. Brown, S. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun. , vol. 39, no. 5, pp. 1183–1210, May 2021

work page 2021
[3]

The throughput of packet broadcasting channels,

N. Abramson, “The throughput of packet broadcasting channels,” IEEE Trans. Commun., vol. COM-25, no. 1, pp. 117–128, 1977

work page 1977
[4]

Unsourced multiple access: A coding paradigm for massive random access,

G. Liva and Y . Polyanskiy, “Unsourced multiple access: A coding paradigm for massive random access,” Proceedings of the IEEE , vol. 112, no. 9, pp. 1214–1229, 2024

work page 2024
[5]

Collision-resolution algorithms and random-access commu- nications,

J. Massey, “Collision-resolution algorithms and random-access commu- nications,” Multi-user communications systems , pp. 73–137, 1981

work page 1981
[8]

Analysis of d-ary tree algorithms with successive interference cancellation,

Q. V ogel, Y . Deshpande, C. Stefanovi ´c, and W. Kellerer, “Analysis of d-ary tree algorithms with successive interference cancellation,” Journal of Applied Probability , vol. 61, no. 3, pp. 1075–1105, Sep. 2024

work page 2024

Show all 16 references

[9]

Status updates over unreliable multiaccess channels,

R. Yates and S. Kaul, “Status updates over unreliable multiaccess channels,” in Proc. IEEE ISIT , 2017

2017
[10]

Age of information in uncoordinated unslotted updating,

——, “Age of information in uncoordinated unslotted updating,” in Proc. IEEE ISIT, 2020

2020
[11]

Analysis of slotted ALOHA with an age threshold,

O. Yavaskan and E. Uysal, “Analysis of slotted ALOHA with an age threshold,” IEEE J. Sel. Areas Commun. , vol. 39, no. 5, pp. 1456–1470, 2021

2021
[12]

Age of information in random access channels,

X. Chen, K. Gatsis, H. Hassani, and S. Bidokhti, “Age of information in random access channels,” IEEE Trans. Inf. Theory , vol. 68, no. 10, pp. 6548–6568, 2022

2022
[13]

Modern random access: an age of information perspective on irregular repetition slotted ALOHA,

A. Munari, “Modern random access: an age of information perspective on irregular repetition slotted ALOHA,” IEEE Trans. Commun., vol. 69, no. 6, pp. 3572–3585, 2021

2021
[14]

The dynamic behavior of frameless ALOHA: Drift analysis, throughput, and age of information,

A. Munari, F. L ´azaro, G. Durisi, and G. Liva, “The dynamic behavior of frameless ALOHA: Drift analysis, throughput, and age of information,” IEEE Trans. Commun. , vol. 71, no. 12, pp. 6914–6927, 2023

2023
[15]

Age of information with collision-resolution random access,

H. Pan, T.-T. Chan, J. Li, and V . C. M. Leung, “Age of information with collision-resolution random access,” IEEE Trans. Veh. Technol., vol. 71, no. 10, pp. 11 295–11 300, 2022

2022
[16]

Gallager, Stochastic Processes: Theory for Applications

R. Gallager, Stochastic Processes: Theory for Applications. Cambridge University Press, 2013

2013

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [6]

Q-ary collision resolution algorithms in random-access systems with free or blocked channel access,

P. Mathys and P. Flajolet, “Q-ary collision resolution algorithms in random-access systems with free or blocked channel access,” vol. 31, no. 2, pp. 217–243, 1985

work page 1985

[2] [7]

High-throughput random access using successive interference cancellation in a tree algorithm,

Y . Yu and G. B. Giannakis, “High-throughput random access using successive interference cancellation in a tree algorithm,” vol. 53, no. 12, pp. 4628–4639, 2007

work page 2007

[3] [1]

Tree algorithms for packet broadcast channels,

J. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Trans. Inf. Theory, vol. 25, no. 5, pp. 505–515, 1979

work page 1979

[4] [2]

Age of information: An introduction and survey,

R. Yates, Y . Sun, D. Brown, S. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun. , vol. 39, no. 5, pp. 1183–1210, May 2021

work page 2021

[5] [3]

The throughput of packet broadcasting channels,

N. Abramson, “The throughput of packet broadcasting channels,” IEEE Trans. Commun., vol. COM-25, no. 1, pp. 117–128, 1977

work page 1977

[6] [4]

Unsourced multiple access: A coding paradigm for massive random access,

G. Liva and Y . Polyanskiy, “Unsourced multiple access: A coding paradigm for massive random access,” Proceedings of the IEEE , vol. 112, no. 9, pp. 1214–1229, 2024

work page 2024

[7] [5]

Collision-resolution algorithms and random-access commu- nications,

J. Massey, “Collision-resolution algorithms and random-access commu- nications,” Multi-user communications systems , pp. 73–137, 1981

work page 1981

[8] [8]

Analysis of d-ary tree algorithms with successive interference cancellation,

Q. V ogel, Y . Deshpande, C. Stefanovi ´c, and W. Kellerer, “Analysis of d-ary tree algorithms with successive interference cancellation,” Journal of Applied Probability , vol. 61, no. 3, pp. 1075–1105, Sep. 2024

work page 2024