PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Wakeup under Costly Collisions

Umesh Biswas, Maxwell Young

arXiv:2609.35662v1cs.DC

TL;DR

Dynamic wakeup must obtain a first successful transmission despite asynchronous arrivals, unknown packet count, and no collision detection, while accounting for collision delay as well as latency. The paper presents Lowball and proves regime-dependent expected-cost guarantees, along with a lower-bound result for age-based batch-fair algorithms.

  • Problem

    Dynamic wakeup seeks a first success with asynchronous packet arrivals and no collision detection, where latency alone does not capture the additional delay charged for collisions.

    Source: §1 · p. 1, §1.1 · p. 2

  • Method

    The paper designs and analyzes Lowball for dynamic wakeup, with collision cost charged separately from slotted execution.

    Source: §1.2 · p. 3, §1.1 · p. 3

  • Results

    For C ≥ K lg^(1/epsilon) n, Lowball has expected latency O(C^(1/2+epsilon) ln C); below that threshold, both expected metrics are O(n log^Theta(1/epsilon) n).

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    The results address latency and collision cost separately, and Lowball does not require n as input or need to identify the applicable regime.

    Source: §1 · p. 1, §1.2 · p. 3

    The analysis assumes no collision detection and allows C to vary with n without specifying a particular dependence.

    Source: §1.1 · p. 2, §1 · p. 2

Abstract

from arXiv · show

The wakeup problem captures a fundamental symmetry-breaking challenge among devices sharing a communication channel. We study the dynamic setting, where packets become active at arbitrary times on a time-slotted multiple access channel. In each slot, a transmission succeeds if and only if exactly one packet transmits; two or more simultaneous transmissions cause a collision. The goal is to obtain a successful transmission quickly. Prior work on wakeup has largely focused on the number of slots until the first success, referred to as the latency. However, a collision may incur substantial additional delay, represented by a per-collision cost $C$. We therefore seek to control both latency and the collision cost of an execution, defined as $C$ times its number of collisions. We design and analyze a randomized algorithm for dynamic wakeup, Lowball, without collision detection or knowledge of the number of packets, $n$. Fix a constant $0<\epsilon\le 1/2$. There is a constant $K>0$ such that, when $C\ge K\lg^{1/\epsilon} n$, Lowball has expected latency $O(C^{1/2+\epsilon}\ln C)$ and expected collision cost $O(\sqrt{C})$. Below this threshold, both expectations are $O(n\log^{\Theta(1/\epsilon)} n)$. These guarantees hold against an adaptive, non-anticipating adversary, and the algorithm succeeds with probability 1. For algorithms in which each packet's transmission probability depends only on $C$ and the packet's local age, with packets activated together using the same probability schedule, we prove that the maximum of expected latency and expected collision cost is $\Omega(\sqrt{C})$.

1 Introduction

The section frames dynamic wakeup as a trade-off between reaching a first success quickly and limiting collision delay under asynchronous packet arrivals. It defines the model and metrics, then presents Lowball’s regime-dependent guarantees and a lower-bound result for a restricted algorithm class.

1 Introduction

  • Dynamic wakeup asks for a first successful transmission despite asynchronous activations, unknown packet count, and no collision detection.Aggressive sending can shorten latency while increasing costly collisions; conservative sending can reduce collision delay while postponing success.Source: §1 · pp. 1–2

1.1 Model and Notation

  • The model has one shared slotted channel, where multiple simultaneous transmissions collide, and packets cannot distinguish an empty slot from a collision.An adaptive adversary chooses activations using prior execution history, but not the fresh random choices or actions of the current slot.Source: §1.1 · p. 2
  • Latency counts slots through the first success, while collision cost separately charges C for each collision slot before that success.The paper allows C to vary with n without assuming a particular dependence.Source: §1 · p. 2, §1.1 · p. 3

1.2 Our Results

  • For C ≥ K lg^(1/epsilon) n, Lowball’s expected latency is O(C^(1/2+epsilon) ln C); below that threshold, both expected metrics are O(n log^Theta(1/epsilon) n).The algorithm does not need n as input or need to determine which regime applies.Source: §1.2 · p. 3
  • The section also establishes a lower bound for age-based batch-fair algorithms, whose packets use the same transmission probability when activated together.The bound concerns the maximum of worst-case expected latency and expected collision cost.Source: §1.2 · pp. 3–4

2 Related Work

Related work covers static and dynamic wakeup, as well as contention resolution in related communication models. The section situates Lowball among latency-focused protocols and notes that prior preliminary versions addressed static wakeup and an early dynamic approach.

2 Related Work

  • In static wakeup, prior results give logarithmic latency bounds without collision detection, while Biswas and Young study per-collision cost C with bounds depending on its size relative to n.With sufficiently large C, their stated expected latency is O(C^(1/2+2epsilon)) and expected collision cost is O(C^(1/2+epsilon)); otherwise both costs are polylogarithmic in n.Source: §2 · p. 4
  • Dynamic wakeup work addresses asynchronous activations and limited information; Jurdziński and Stachowiak give an Omega(log^2 n) expected-latency lower bound and a matching upper bound under a polynomial upper bound on n.For unknown n without a global clock, collision detection, or identifiers, Jurdziński and Stachowiak give O(n/log n) latency with fixed constant error probability.Source: §2 · p. 4
  • The present paper strengthens preliminary results: the MUSICAL paper studied static wakeup, while the DSN Doctoral Forum paper reported an early dynamic approach.The current work provides a full dynamic algorithm and analysis establishing Theorem 1’s guarantees.Source: §2 · pp. 4–5
  • Related dynamic contention-resolution work studies asynchronous arrivals and no collision detection, but DecreaseSlowly’s O(k) wakeup time w.h.p. does not target collision cost.Contention resolution requires all active packets to succeed, unlike wakeup, which requires only one successful transmission.Source: §2 · p. 5

3 Algorithm Specification

Lowball combines a deliberately low initial sending probability with growing and shrinking phases to manage latency and collision cost under dynamic packet activations. Its bounds depend on the collision cost C, with a separate guarantee below the large-C threshold.

3 Algorithm Specification

  • Each iteration pairs a growing phase, which geometrically raises sending probability, with a shrinking phase, which geometrically lowers it; shrinking phases double in length across iterations.The schedule starts at 1/w0 = 2^-C^ϵ, with w0 = 2C^ϵ; growing phases have fixed length.Source: §3 · pp. 5–6

A Baseline via Backoff.

  • Unlike backoff starting at probability 1/2, which can incur Ω(C) expected collision cost when two packets begin together, Lowball starts with a deliberately low probability.The unknown packet count n makes choosing how low to start a challenge.Source: §3 · p. 5, A Baseline via Backoff · p. 6

Design Choices and Overview.

  • O(C^(1/2+ϵ) ln C) expected latency and O(√C) expected collision cost hold for C ≥ K lg^(1/ϵ) n; below it, both are O(n log^Θ(1/ϵ) n).The analysis distinguishes the regimes; Lowball uses the same schedule in both.Source: Design Choices and Overview · p. 7
  • In the dynamic setting, other batches’ growth can interrupt declining contention, but sufficiently long shrinking phases contain m consecutive good-contention slots.Completing j sufficiently late shrinking phases without success requires surviving at least jm good-contention slots, making the event probability decrease geometrically in j.Source: Design Choices and Overview · p. 7
  • Lowball targets contention of order 1/C, balancing success probability of order 1/C against collision probability O(1/C).For m = Θ(C ln C) good-contention slots, the probability of no success is at most C^−αd/e, motivating the chunk length.Source: Design Choices and Overview · pp. 7–8
  • Smaller ϵ shortens each growing phase and improves the large-C latency bound, but raises the threshold exponent 1/ϵ and the small-C polylogarithmic exponent.The analysis restricts ϵ to 0 < ϵ ≤ 1/2.Source: Design Choices and Overview · p. 8

4 Upper-Bound Analysis

The upper-bound analysis handles adaptive activations by conditioning on pre-transmission histories, then uses contention behavior across Lowball’s phases to bound latency and collisions. It establishes expected latency and collision-cost bounds across two regimes of collision cost C, accounting for low-, good-, and high-contention slots.

4.1 Preliminaries and Helper Lemmas

  • A reachable pre-transmission history records prior activations, transmissions, and outcomes plus the current activation decision, fixing the active packets and their sending probabilities.This history excludes transmission decisions in the current slot, supporting conditional analysis against an adaptive adversary.Source: §4.1 · p. 9
  • Equal probabilities maximize the sum of products of any fixed number of distinct probabilities when their total is fixed.Lemma 3 states the maximum occurs at p1 = p2 = ··· = pN = λ/N.Source: §4.1 · p. 9
  • O(1/C) bounds the conditional collision probability in any reachable slot with low or good contention.The estimate applies after conditioning on a pre-transmission history, when active packets’ sending probabilities are fixed.Source: §4.1 · pp. 10–11

4.2 Latency Analysis

  • For every k ≥ k*, a completed shrinking phase S_k contains m consecutive good-contention slots, where k* = ⌈lg n + ϵ lg C + 3 lg lg n + c⌉.Here c is a sufficiently large constant; the proof obtains these slots inside a clean shrinking window.Source: §4.2 · p. 13
  • O(nC^(1/2+2ϵ) ln C lg^3 n) bounds expected remaining slots from any reachable history during or immediately after the first initial growing phase.The bound includes the current slot and holds for histories with 1 ≤ s ≤ g + 1.Source: §4.2 · p. 13
  • exp(−m/(8e)) bounds the probability of completing the first batch’s initial growing phase without success when C ≥ K lg^(1/ϵ) n.K is a sufficiently large constant depending only on ϵ.Source: §4.2 · p. 14
  • After the first growing phase, the expected latency contribution from continued execution is O(1).The analysis uses exponential decay to dominate the remaining C^(1/2+5ε) ln C factor.Source: §4.2 · p. 16

4.3 Collision Cost Analysis

  • For low- or good-contention slots, collision probability is O(λ^2), while success probability is at least λe^(-2λ), for contention λ.These conditional probability bounds support the analysis of collision cost in those slots.Source: §4.3 · p. 16
  • When C ≥ K lg^(1/ε) n, the expected collision cost from high-contention slots is O(1).The analysis splits these slots around the first batch’s initial growing phase.Source: §4.3 · pp. 16–18
  • For C ≥ K lg^(1/ε) n, Lowball’s expected latency is O(C^(1/2+ε) ln C) and expected collision cost is O(√C); below that threshold, both are O(n log^Θ(1/ε) n).The theorem assumes fixed 0 < ε ≤ 1/2 and a sufficiently large constant K depending only on ε.Source: §4.3 · p. 19

5 Lower Bound

For age-based batch-fair algorithms, latency and collision cost obey a product lower bound, limiting how small both can be. A classical latency lower bound applies when C is fixed as n grows, but its constants may depend on C.

5.1 Tradeoff: Latency & Expected Collision Cost

  • For every age-based batch-fair algorithm with finite worst-case latency, LA(n, C)KA(n, C) ≥ C/4, so the maximum of the two expectations is Ω(√C).Packets activated together use the same age-based probability schedule; probabilities may depend on C, but not on n, global time, or prior transmission outcomes.Source: §5.1 · pp. 20–21, §5 · p. 20
  • In the large-C regime, Lowball’s maximum of expected latency and collision cost is within O(C^ε ln C) of the best possible for the age-based batch-fair class.The comparison is stated for C ≥ K(lg^(1/ε) n).Source: §5 · p. 20, §5.1 · p. 21

5.2 The Classical Dynamic Lower Bound for Fixed Per-Collision Cost

  • When C is fixed independently of n, the adapted classical construction gives an Ω(n/log n) expected-latency lower bound, with constants and the required threshold on n potentially depending on C.The construction adapts the batch-injection argument of Jurdziński and Stachowiak [23].Source: §5.2 · p. 22, C) lower bound · p. 22
  • The fixed-C lower bound does not yield an Ω(n/log n) term with a hidden constant independent of C when C varies with n.Packets know C, so their probability schedules may change with C; the fixed-C asymptotic argument therefore does not contradict the large-C upper bounds.Source: §5.2 · p. 22, C) lower bound · p. 23

6 Conclusion and Future Work

The paper studies dynamic wakeup with per-collision cost and no collision detection, and reports bounds on both latency and collision cost. For the considered algorithm class, the large-C upper bound is within a factor of the lower bound, leaving a gap whose reduction and extension remain open.

  • The results address dynamic wakeup with per-collision cost and no collision detection, bounding both latency and collision cost under arbitrary packet activations.Source: §6 · p. 23
  • In the large-C regime, Lowball’s upper bound for the maximum of its two expectations is within O(C^ε ln C) of the lower bound for the considered algorithm class.Source: §6 · p. 23
  • Whether the gap can be reduced or eliminated, and whether the lower bound extends beyond age-based batch-fair algorithms, remain open questions.Source: §6 · p. 23
Loading 2609.35662v1…