PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Collision-Free Acquisition in 1-Persistent Age-Threshold Slotted ALOHA via Role-Protected Counters

Plínio Santini Dester

arXiv:2609.09934v1cs.ITmath.IT

TL;DR

1-pTSA can acquire a periodic collision-free schedule, but its acquisition transient can dominate finite-horizon performance. RP–CTSA separates reservation memory from AoI and protects scheduled singleton phases, yielding exact acquisition laws and reported finite-horizon AoI gains over 1-pTSA.

  • Problem

    Although 1-pTSA can self-organize into a periodic collision-free schedule, its acquisition transient can dominate finite-horizon performance.

    Source: §I · p. 1

  • Method

    RP–CTSA separates reservation memory from AoI, protects scheduled singletons, and releases scheduled cohorts of two or more using a binary RELEASE/HOLD decision.

    Source: §I · p. 2

  • Results

    At Γ_n = n, Eτ_n ∼ π^2n^2/(6c); when Γ_n/n → 1 + θ, τ_n/(n log n) and Eτ_n/(n log n) converge to (1+θ)/(cθ).

    Source: §I · p. 2

  • Takeaways & Limitations

    RP–CTSA preserves every collision-free schedule while its shorter acquisition transients translate into finite-horizon AoI gains over 1-pTSA.

    Source: §VI · p. 8

    The analysis assumes error-free role classification and feedback; persistent errors can invalidate the monotone acquisition argument.

    Source: C. Proposed protocol: RP–CTSA · p. 3

Abstract

from arXiv · show

Goal-oriented sensing, estimation, and control benefit from prompt, regular access to task-relevant updates. Although 1-persistent age-threshold slotted ALOHA (1-pTSA) can self-organize into a periodic collision-free schedule, its acquisition transient can dominate finite-horizon performance. We propose role-protected counter-threshold slotted ALOHA (RP--CTSA), which separates reservation memory from the age of information (AoI). A scheduled singleton retains its phase after colliding with active contenders, whereas a collision involving multiple scheduled nodes releases them immediately; AoI resets only after a decoded update. The protocol requires individual acknowledgments and a binary RELEASE/HOLD indication, but no centralized phase assignment or identification of colliders. Let $n$ denote the number of nodes and $\Gamma_n$ the counter threshold. Under inverse-population access scaling, the acquisition dynamics admit an exact pure-death representation. When $\Gamma_n=n$, the acquisition time is $O(n^2)$; when $\Gamma_n\sim(1+\theta)n$, with $\theta>0$, it is $O(n\log n)$. Simulations confirm both regimes and show substantial finite-horizon AoI gains over 1-pTSA while preserving every collision-free schedule.

I. Introduction

The paper targets the long acquisition transient of 1-pTSA, where active collisions can destroy learned phases, and proposes RP–CTSA to protect scheduled singletons while releasing unresolved cohorts. It analyzes distributed access with separate reservation counters and AoI, deriving exact acquisition laws and reporting finite-horizon AoI gains over 1-pTSA.

I. Introduction

  • The analysis distinguishes stationary freshness from task utility: AoI measures timeliness, but does not universally measure downstream task performance.RP–CTSA supplies predictable transmission opportunities without determining semantic relevance or task utility.Source: §I · p. 1
  • In 1-pTSA, an active collision can make a scheduled singleton miss its ACK and return to contention, destroying its learned phase and delaying acquisition.The setting uses a fixed finite population with Bernoulli access by active nodes, addressed ACKs, and no centralized phase assignment.Source: §I · p. 1
  • RP–CTSA preserves a scheduled singleton's phase through active collisions, releases scheduled cohorts of two or more immediately, and resets AoI only after a decoded update.A binary RELEASE/HOLD decision and individual acknowledgments support the distributed protocol without phase assignment or collider identification.Source: §I · p. 2
  • Role protection makes acquisition a monotone pure-death process after binaryization: each state change removes one active node, and holes equal active nodes plus slack.The exact finite-n chain is analyzed before taking large-population limits, rather than using a mean-field closure.Source: §I · p. 2
  • At Γ_n = n, Eτ_n ∼ π^2n^2/(6c); when Γ_n/n → 1 + θ, τ_n/(n log n) and Eτ_n/(n log n) converge to (1+θ)/(cθ).The synchronized-start analysis gives a quadratic law at critical packing and an n log n law with linear slack.Source: §I · p. 2

B. Baseline: 1-pTSA

In 1-pTSA, a failed threshold attempt makes a scheduled node active, so its learned phase is lost. RP–CTSA separates reservation memory from AoI and uses role feedback to preserve singleton phases while releasing scheduled cohorts that collide with one another.

B. Baseline: 1-pTSA

  • In 1-pTSA, a failed deterministic threshold attempt loses its ACK and makes the node active, so the learned phase is lost.The node then attempts independently with probability p_n until succeeding.Source: B. Baseline: 1-pTSA · p. 3

C. Proposed protocol: RP–CTSA

  • RP–CTSA gives scheduled nodes explicit reservation counters separate from AoI, while active nodes without a reserved phase attempt independently with probability p_n.Counter updates occur after the slot, so a preserved reservation returns after Γ_n slots.Source: C. Proposed protocol: RP–CTSA · p. 3
  • A scheduled singleton retains its phase when active attempts collide with it, while two or more due scheduled nodes are released immediately to random access.The role probe lets the receiver distinguish the number of due scheduled nodes through idle, singleton, or collision outcomes and broadcast RELEASE/HOLD without identifying transmitters.Source: C. Proposed protocol: RP–CTSA · p. 3
  • The role probe requires reserved control airtime, minislot synchronization, and error-free role classification and feedback; persistent errors can invalidate monotone acquisition.False RELEASE can destroy a singleton reservation, while false HOLD can preserve a colliding scheduled cohort.Source: C. Proposed protocol: RP–CTSA · p. 3

D. Acquisition and performance metrics

The section defines acquisition in terms of reservation states, establishes an invariant collision-free regime, and shows finite-mean acquisition with slack-dependent dynamics.

D. Acquisition and performance metrics

  • The acquisition configuration tracks the active set and labeled cyclic reservation word, not unbounded AoI; the main theorems start with all nodes due together.For 1-pTSA, acquisition means no active nodes and distinct implicit threshold phases modulo Γn.Source: D. Acquisition and performance metrics · p. 4

III. Preserved Deterministic Regime

  • Normalized average AoI tends to 1/2 at Γn = n and to 1 at Γn ∼2n.Every collision-free state remains invariant up to cyclic phase rotation, with throughput n/Γn and one success per node every Γn slots.Source: §III · p. 4

IV. Slack-Dependent Acquisition Analysis

  • For fixed n, Γn ≥n, and 0 < pn < 1, immediate-release RP–CTSA reaches a collision-free state almost surely with finite mean from every admissible start.An admissible state places each node exactly once, either in the active set or in a reservation phase.Source: §IV · p. 4, D. Acquisition and performance metrics · p. 4
  • After at most one frame, every scheduled phase is empty or singleton; thereafter each state change removes one active node.The number of holes equals the active-node count plus slack sn, and a unique active transmission at a hole creates a singleton reservation.Source: §IV · p. 4

A. Exact arrangement-free frame chain

At frame boundaries, the acquisition process has an exact pure-death kernel determined by the number of holes, not their cyclic arrangement. An opportunity-time construction relates this chain to acquisition in calendar slots.

A. Exact arrangement-free frame chain

  • State zero is absorbing, and the opportunity-weighted work is bounded through the number of deaths across frames.A frame beginning with m active nodes uses sn + m opportunities; the deterministic comparison is used in Theorem 6.Source: A. Exact arrangement-free frame chain · pp. 4–5
  • Given Mk = m, the next frame contains exactly sn + m holes, and these determine the transition kernel of the frame-boundary chain.The kernel applies without phase mixing or a uniformly random reservation word.Source: A. Exact arrangement-free frame chain · pp. 4–5
  • The opportunity-time construction defines Wn as dimensionless opportunity-weighted work, with calendar slots obtained by multiplying by Γn.For sn > 0, the first frame boundary after absorption is Kn; the construction also gives Kn−1 ≤Wn when sn = 0.Source: A. Exact arrangement-free frame chain · p. 5

B. Fixed slack: a distributional entrance law

For the synchronized start under fixed slack and inverse-population access scaling, the acquisition time has a distributional limit. The limit is represented by a convergent series, with a specified exponential rate for each fixed defect level.

B. Fixed slack: a distributional entrance law

  • The fixed-slack limit series converges almost surely and in every Lk of fixed order.The series representation is given for Ts in equation (13).Source: B. Fixed slack: a distributional… · p. 5
  • The resulting Laplace-transform expression is strictly positive and real, and is independent of the square-root branch.When its arguments are complex conjugates, the numerator is the squared modulus of a gamma-function value.Source: B. Fixed slack: a distributional… · p. 5
  • At fixed defect level m, calendar holding time divided by n^2 approaches an exponential variable of rate cm(m + s).The theorem assumes sn →s in the nonnegative integers and npn →c in (0, ∞), from the synchronized start.Source: B. Fixed slack: a distributional… · pp. 5–6

C. Diverging slack: concentration and crossover

The section derives a synchronized-start limit law for diverging slack and explains how added holes change the late-stage removal rate.

C. Diverging slack: concentration and crossover

  • The proof separates a lower-order early region from a small-active region where hole-opportunity and calendar clocks agree to leading order.No phase-mixing or random-arrangement assumption is needed; the opportunity-time variance is smaller than (β⋆n)^2 by order (log sn)^-2.Source: C. Diverging slack: concentration and… · p. 6
  • c n log n is the acquisition scale when Γn/n→2 under Theorem 6's assumptions.Those assumptions include diverging slack, bounded Γn/n, and npn→c.Source: C. Diverging slack: concentration and… · p. 6
  • With linear slack, even the final defect sees Θ(n) holes and is removed at rate of order m/n, unlike the critical case's order m^2/n^2 rate.Summing reciprocal rates changes the critical n^2 scale to a harmonic n log n law.Source: C. Diverging slack: concentration and… · p. 6
  • The specific limit laws apply only to synchronized starts; arbitrary admissible starts have finite-system absorption but require further analysis for those laws.After at most one frame, remaining phases are binary.Source: C. Diverging slack: concentration and… · p. 6

V. Numerical Results

The simulations corroborate the predicted slack-dependent acquisition scales, including the linear-slack slope, while showing close agreement with finite-sum predictions for fixed slack.

V. Numerical Results

  • Two independent simulators test acquisition and AoI: an exact event-skipping simulator and a slot-exact engine comparing 1-pTSA, RP–CTSA, and L-ZC.The event-skipping simulator reaches n=65,536 for principal regimes.Source: §V · p. 6

A. Slack crossover

  • Means for fixed slack s=0, 1, 5 and sublinear slack sn=⌊√n⌋ approach one when normalized by tΣ,n.Panel (a) shows the normalized event-skipping means.Source: A. Slack crossover · p. 6, Figure 1 · p. 7
  • At c=2.5, Eτn/n^2 estimates were 0.65798, 0.39922, and 0.18263 for s=0, 1, and 5, versus theoretical 0.65797, 0.40000, and 0.18267.The estimates combine high-precision results at n=16384 and 32768.Source: A. Slack crossover · p. 6
  • The access intensity c=2.5 is representative, not optimized; optimizing it would require a separate collision or energy objective.The theorems hold for arbitrary fixed c∈(0,∞) and display explicit 1/c dependence.Source: A. Slack crossover · pp. 6–7
  • Fitted slopes were 1.2121 at sn/n→1/2 and 0.8044 at Γn=2n, versus theoretical 1.2000 and 0.8000, respectively.Panel (b) compares Eτn/n against log n.Source: A. Slack crossover · p. 6, Figure 1 · p. 7

B. Finite-horizon freshness

Finite-horizon comparisons show RP–CTSA gains over 1-pTSA under synchronized and random-phase starts, with L-ZC serving as an information-richer benchmark. The conclusion leaves imperfect role detection and task-specific utility beyond AoI for future work.

B. Finite-horizon freshness

  • The comparison uses n=32, a synchronized collision start, and p_n=2.5/n for 1-pTSA and RP–CTSA; L-ZC is an information-advantaged benchmark.L-ZC uses each node's outcome, the preceding-frame idle map, frame synchronization, and knowledge of n.Source: B. Finite-horizon freshness · p. 7
  • RP–CTSA improves substantially over 1-pTSA using less global information, while preserving collision-free logical-slot throughput and AoI.L-ZC's complete preceding-frame idle map gives it an additional advantage at critical packing.Source: B. Finite-horizon freshness · p. 7, §VI · p. 8
  • By 2n log n, acquired fractions are 0.9653 for RP–CTSA, 0.8378 for L-ZC, and 0.3378 for 1-pTSA; both RP–CTSA and L-ZC reach one by 4n log n.At 16n log n, normalized AAoI is 1.093 for RP–CTSA, 1.226 for L-ZC, and 1.137 for 1-pTSA.Source: B. Finite-horizon freshness · p. 7

C. Robustness and censoring

  • At Γ_n=2n−1 and ℓ=4n log n, iid random phases shift normalized AAoI from 1.512 to 1.242 (1-pTSA), 1.372 to 1.118 (RP–CTSA), and 1.903 to 1.186 (L-ZC).This robustness experiment does not replace the synchronized-start limit theorem.Source: C. Robustness and censoring · p. 7

B. Finite-horizon freshness

VI. Conclusion

  • Imperfect role detection and task-specific utility beyond AoI remain future-work directions.Source: §VI · p. 8

Appendix A Proof of Theorem 5

The proof analyzes fixed defect levels and then removes the truncation by bounding the entrance-time remainder. This yields weak convergence and convergence of the first two moments.

  • For fixed truncation level m*, cyclic counting and the frame kernel establish convergence of the scaled holding times and their moments.For every fixed m, n g_n,m converges to c_m.Source: Appendix A · pp. 8–9
  • The n^-2-scaled entrance-time remainder vanishes in L2 as n grows and then m* increases, controlling the time before the truncated regime.The proof uses a one-sided frame-packing bound on the pre-m* calendar time.Source: Appendix A · p. 9
  • Equations (27)–(29) establish weak convergence and convergence of the first two moments.The argument combines uniformly L2-bounded finite-dimensional variables with a uniformly L2-small entrance remainder.Source: Appendix A · p. 9

Appendix B Proof of Theorem 6

The proof uses moments of exact weighted work and bounds that distinguish slack ranges. An exact harmonic identity then yields the stated expansions.

  • The analysis begins with the exact weighted work W_n and its first two moments, accounting for the finite-n access factor in numerical centering.That factor does not affect the leading law.Source: Appendix B · p. 9
  • For diverging slack s=O(n), the proof bounds variance terms separately for s≤n and s>n.The associated lower bounds on σ_n,s use different expressions in those two ranges.Source: Appendix B · p. 9
  • Expanding the exact harmonic identity (20) yields (22) and (23).Source: Appendix B · p. 9
Loading 2609.09934v1…