pith. sign in

arxiv: 2604.13428 · v1 · submitted 2026-04-15 · 💻 cs.DS

Online TCP Acknowledgment under General Delays

Sujoy Bhore , Micha{\l} Paw{\l}owski , Seeun William Umboh This is my paper

Pith reviewed 2026-05-10 12:38 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmscompetitive analysisTCP acknowledgmentdelay costsbatchingmonotone functionscompetitive ratioonline computation
0
0 comments X

The pith

The deterministic competitive ratio for online TCP acknowledgment with sum batch delays is Theta(log n) under only monotonicity of the delay function.

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

The paper generalizes the classic online TCP acknowledgment problem to batch-oblivious and batch-aware delay cost models. In the batch-aware model where total cost sums the per-batch delay functions f applied to each batch's packet delay vector, it shows that a simple greedy strategy is Omega(n)-competitive while a more refined deterministic algorithm achieves a tight Theta(log n) ratio. This holds under the minimal assumption that f is monotone. The work also establishes 2-competitive guarantees for batch-oblivious submodular or lp-norm delays and for batch-aware maximum costs. The result clarifies the limits of online batching decisions when delay penalties accumulate across groups rather than globally.

Core claim

For the batch-aware setting where the overall delay cost is the sum of the batch delay costs, the deterministic competitive ratio is Theta(log n). The algorithm achieves the O(log n) upper bound using only the assumption that the per-batch delay function f is monotone, while a matching Omega(log n) lower bound holds for any deterministic online algorithm; separately, the classic greedy rule is Omega(n)-competitive in this model.

What carries the argument

A deterministic online algorithm that selects acknowledgment times to achieve O(log n) competitiveness, relying solely on the monotonicity of the per-batch delay function f.

If this is right

  • The classic greedy algorithm, which acknowledges when pending delay equals acknowledgment cost, becomes Omega(n)-competitive under summed batch delays.
  • Deterministic algorithms achieve 2-competitive ratio for batch-oblivious models using continuous submodular functions or lp norms.
  • Deterministic algorithms achieve 2-competitive ratio for batch-aware models when overall cost is the maximum batch delay cost.
  • The Theta(log n) bound is tight and requires no stronger assumptions on f beyond monotonicity.

Where Pith is reading between the lines

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

  • Logarithmic competitiveness may extend to other online batching problems that accumulate vector delay costs additively rather than globally.
  • Randomized algorithms might improve upon the deterministic log n bound in the sum batch-aware model.
  • The approach could be tested on related problems such as generalized joint replenishment with monotone per-batch costs.

Load-bearing premise

The per-batch delay cost function f is monotone, meaning non-decreasing in each coordinate of the packet delay vector.

What would settle it

A concrete sequence of packet arrivals of size n on which any deterministic online algorithm exceeds c log n times the optimal offline cost for arbitrarily large constant c.

read the original abstract

In a seminal work, Dooly, Goldman, and Scott (STOC 1998; JACM 2001) introduced the classic Online TCP Acknowledgment problem. In this problem, a sequence of $n$ packets arrives over time, and the objective is to minimize both the number of acknowledgments sent and the total delay experienced by the packets. They showed that a greedy algorithm -- acknowledge when the delay of pending packets equals the acknowledgment cost -- is $2$-competitive. Online TCP Acknowledgment is the canonical online problem with delay, capturing the fundamental tradeoff between reducing service cost through batching and the delay incurred by pending requests. Prior work has largely focused on different types of service costs, e.g., Joint Replenishment. However, to the best of our knowledge, beyond the work of Albers and Bals (SODA 2003), which studies maximum delay and closely related objectives, not much is known for more general delay cost models. In this work, we study the Online TCP Acknowledgment under two new generalized delay costs that we call batch-oblivious and batch-aware. In the former, the delay cost is a function of the vector of packet delays. We show that the classic greedy approach is also $2$-competitive for continuous submodular functions and $\ell_p$ norms. In the batch-aware model, each batch incurs a delay cost that is a function $f$ of the vector of delays incurred by its packets. When the overall delay cost is the maximum of the batch delay costs, we show that the greedy approach is also $2$-competitive. Our main technical contribution is for the batch-aware setting, where the overall delay cost is the sum of the batch delay costs. We show that the greedy approach is $\Omega(n)$-competitive and that the deterministic competitive ratio is $\Theta(\log n)$. Remarkably, our algorithm only requires the bare minimum assumption that $f$ is monotone.

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 / 4 minor

Summary. The manuscript extends the classic Online TCP Acknowledgment problem to batch-oblivious and batch-aware generalized delay cost models. For batch-oblivious costs, the greedy algorithm is shown to be 2-competitive for continuous submodular functions and ℓ_p norms. In the batch-aware model, greedy remains 2-competitive for the maximum objective, while for the sum objective the paper proves that greedy is Ω(n)-competitive and presents a new algorithm achieving a tight Θ(log n) deterministic competitive ratio under the sole assumption that each per-batch delay function f is monotone.

Significance. If the stated bounds hold, the work meaningfully generalizes the canonical 2-competitive TCP acknowledgment result to broader delay cost families while isolating the effect of batch awareness. The Θ(log n) bound for the sum objective, obtained with only monotonicity, is a clean and potentially reusable technical contribution that cleanly separates the batch-aware sum case from both the classic model and the batch-oblivious setting. The use of standard potential-function and charging arguments, together with matching lower bounds via adversarial packet sequences, strengthens the overall analysis.

minor comments (4)
  1. [Abstract] Abstract: the distinction between batch-oblivious and batch-aware models is introduced without a one-sentence definition; adding a brief parenthetical clarification would improve accessibility.
  2. [Model] Model section: the precise definition of the per-batch delay function f (domain, monotonicity, and how the vector of delays within a batch is formed) should be stated once with explicit notation before any competitive-ratio claims are made.
  3. [Batch-aware sum lower bound] Lower-bound construction for Ω(log n): a short worked example with 3–4 packets illustrating how the adversary forces the logarithmic ratio under a monotone f would make the argument easier to follow.
  4. [Introduction] Related-work paragraph: the comparison to Albers and Bals (SODA 2003) on maximum delay could be expanded by one sentence to emphasize how the new sum result differs from their max-delay analysis.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the clear summary of our contributions, and the recommendation for minor revision. We appreciate the recognition that the Θ(log n) bound under monotonicity is a clean technical contribution separating the batch-aware sum case from prior models.

Circularity Check

0 steps flagged

No significant circularity; standard competitive analysis

full rationale

The paper derives its competitive ratios (2-competitive for several cases, Θ(log n) for the batch-aware sum model) via explicit algorithm design (greedy and a new deterministic algorithm) and direct analysis against an optimal offline solution, using the monotonicity assumption on f to bound costs. No parameters are fitted to data, no result is renamed or smuggled via self-citation, and the lower bounds are constructed via adversarial arrivals independent of the upper-bound proofs. The derivation chain is self-contained against the problem definition and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard online-algorithm assumptions (adversarial arrival sequence, competitive ratio measured against optimal offline) plus the monotonicity of f; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • standard math Competitive ratio is defined with respect to an optimal offline solution that knows the entire input sequence in advance.
    Invoked in the definition of the problem and all stated bounds.
  • domain assumption The per-batch delay function f is monotone non-decreasing.
    Explicitly stated as the only assumption needed for the log n algorithm.

pith-pipeline@v0.9.0 · 5669 in / 1339 out tokens · 24252 ms · 2026-05-10T12:38:22.280946+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

20 extracted references · 20 canonical work pages

  1. [1]

    Min-cost bipartite perfect matching with de- lays.Approximation, Randomization, and Combinatorial Optimization

    [AAC+17] Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect matching with de- lays.Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), 81:1,

    work page 2017

  2. [2]

    Dynamic TCP acknowledgement: penalizing long delays

    [AB03] Susanne Albers and Helge Bals. Dynamic TCP acknowledgement: penalizing long delays. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pages 47–55. ACM/SIAM,

    work page 2003

  3. [3]

    Set cover with delay - clair- voyance is not required

    [ACKT20] Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou. Set cover with delay - clair- voyance is not required. In28th Annual European Symposium on Algorithms, ESA 2020, September 18 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 ofLIPIcs, pages 8:1–8:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2020

  4. [4]

    Online joint replenishment problem with arbitrary holding and backlog costs

    [AL26] Yossi Azar and Shahar Lewkowicz. Online joint replenishment problem with arbitrary holding and backlog costs. InProceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, Canada, January 11-14, 2026, pages 2702–2725. SIAM,

    work page 2026

  5. [5]

    The min-cost matching with concave delays problem

    [ARV21] Yossi Azar, Runtian Ren, and Danny Vainstein. The min-cost matching with concave delays problem. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 301–320. SIAM,

    work page 2021

  6. [6]

    General framework for metric optimization problems with delay or with deadlines

    [AT19] Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. InProceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 60–71. IEEE Computer Society,

    work page 2019

  7. [7]

    Better approximation bounds for the joint replenishment problem

    [BBC+14] Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, and Jirí Sgall. Better approximation bounds for the joint replenishment problem. InProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 42–54. SIAM,

    work page 2014

  8. [8]

    InProceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1235–1244

    [BFNT17] Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon.O(depth)-competitive algorithm for online multi-level aggregation. InProceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1235–1244. SIAM,

    work page 2017

  9. [9]

    19 [BKV04] Carlos Brito, Elias Koutsoupias, and Shailesh Vaya. Competitive analysis of organization net- works or multicast acknowledgement: how much to wait? InProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 627–635. SIAM,

    work page 2004

  10. [10]

    Online weighted cardinality joint replenishment problem with delay

    [CKU22] Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh. Online weighted cardinality joint replenishment problem with delay. In49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 40–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    work page 2022

  11. [11]

    Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae

    [CPSV18] Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, and José Verschae. The online set aggregation problem. InLATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 ofLecture Notes in Computer Science, pages 245–259. Springer,

    work page 2018

  12. [12]

    Online matching with set and concave delays

    [DU23] Lindsey Deryckere and Seeun William Umboh. Online matching with set and concave delays. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, AP- PROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA, volume 275 ofLIPIcs, pages 17:1–17:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2023

  13. [13]

    The power of clairvoyance for multi- level aggregation and set cover with delay

    [LUX23] Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie. The power of clairvoyance for multi- level aggregation and set cover with delay. InProceedings of the 2023 Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA), pages 1594–1610. SIAM,

    work page 2023

  14. [14]

    The parking permit problem

    [Mey05] Adam Meyerson. The parking permit problem. In46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, Pittsburgh, P A, USA, October 23-25, 2005, Proceedings, pages 274–

    work page 2005

  15. [15]

    Putting off the catching up: Online joint replen- ishment problem with holding and backlog costs

    [MNR25] Benjamin Moseley, Aidin Niaparast, and R Ravi. Putting off the catching up: Online joint replen- ishment problem with holding and backlog costs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3865–3883. SIAM,

    work page 2025

  16. [16]

    Submodular norms with applications to online facility location and stochastic probing

    20 [PRS23] Kalen Patton, Matteo Russo, and Sahil Singla. Submodular norms with applications to online facility location and stochastic probing. InApproximation, Randomization, and Combinatorial Op- timization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA, volume 275 ofLIPIcs, pages 23:1–23:22. Schloss Dagstuh...

    work page 2023

  17. [17]

    [Sei00] Steven S. Seiden. A guessing game and randomized online algorithms. InProceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 592–601. ACM,

    work page 2000

  18. [18]

    Improved online algorithms for inventory management problems with holding and delay costs: Riding the wave makes things simpler, stronger, & more general

    [SU26] David Shmoys and Varun Suriyanarayana Seeun William Umboh. Improved online algorithms for inventory management problems with holding and delay costs: Riding the wave makes things simpler, stronger, & more general. InProceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, Canada, January 11-14, 2026, pages 2726–2742. SIAM,

    work page 2026

  19. [19]

    Nearly-tight lower bounds for set cover and network design with dead- lines/delay

    [Tou21] Noam Touitou. Nearly-tight lower bounds for set cover and network design with dead- lines/delay. In32nd International Symposium on Algorithms and Computation, ISAAC 2021, De- cember 6-8, 2021, Fukuoka, Japan, volume 212 ofLIPIcs, pages 53:1–53:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2021

  20. [20]

    Frameworks for nonclairvoyant network design with deadlines or delay

    [Tou23] Noam Touitou. Frameworks for nonclairvoyant network design with deadlines or delay. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 ofLIPIcs, pages 105:1–105:20. Schloss Dagstuhl - Leibniz- Zentrum für Informatik,

    work page 2023