- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies online acknowledgment with an objective combining ACK costs and the sum of batch-wise maximum delays. Each arrival reveals a prediction of the next arrival time. The proposed learning-augmented Alarm algorithm has an error-dependent competitive-ratio upper bound, with consistency and robustness . The paper additionally claims a universal deterministic lower bound establishing Pareto optimality and evaluates the algorithm on synthetic and real packet traces.
Critical strengths
The paper considers a meaningful prediction interface for a classical acknowledgment objective. The proposed timer-based algorithm is simple, and its explicit error-dependent upper bound provides a concrete characterization of its behavior under imperfect next-arrival predictions.
Critical weaknesses
Theorem 5.4 is false under the stated model, invalidating the claimed universal Pareto optimality.
First, Appendix A.3, lines 690–695, omits the fixed ACK cost from the offline solution and does not account for the algorithm's subsequent ACK. Consequently, the displayed ratio does not establish the claimed lower bound.
More importantly, the following deterministic algorithm contradicts the theorem. Normalize the ACK cost and the critical interarrival gap to . Initially, operate in a trusting mode:
- If the predicted next gap exceeds , acknowledge immediately.
- Otherwise, wait for the next arrival, but acknowledge after a timeout of if no arrival occurs.
- Upon the first detected gap-classification error, switch permanently to Classic, which waits after the most recent arrival and resets its timer on each arrival.
A classification error is detectable online: either a predicted short gap times out, or a predicted long gap is followed by an arrival within .
For a nonempty finite input with consecutive gaps , the offline optimum is
Each gap can independently be covered by waiting across it or separated by an additional ACK. Under perfect predictions, the proposed fallback algorithm makes exactly these optimal choices, including an immediate final ACK, so it is -consistent.
For arbitrary predictions, use the paper's gap-wise cost decomposition. Correct classifications before the switch incur the corresponding optimal gap cost. A short prediction followed by a long gap incurs cost , twice its optimal gap cost. A long prediction followed by a short gap incurs cost , exceeding twice its optimal gap cost by at most . After the switch, Classic incurs at most twice the corresponding optimal gap costs, including a terminal cost of at most . Thus,
since .
This gives a -consistent, -robust deterministic algorithm. Taking contradicts Theorem 5.4, which requires robustness at least whenever consistency does not exceed . The construction requires neither future information nor knowledge of the input length or prediction error.
This counterexample does not claim the same smoothness guarantee as Augmented Alarm. However, Theorem 5.4 quantifies over all deterministic algorithms without imposing such an additional requirement.
Questions for authors
-
Does the stated model exclude the fallback algorithm above? If so, please identify the precise restriction. Otherwise, how should Theorem 5.4 and the associated Pareto-optimality claims be revised?
-
After removing the universal optimality claim, what substantive optimality result remains beyond the analysis of the proposed timer family? Please distinguish algorithm-specific tightness from lower bounds applying to all deterministic algorithms.
2 comments
Dear Reviewer,
As the discussion period is approaching its end, we wanted to kindly follow up regarding our response and revised manuscript.
We sincerely appreciate your identification of the counterexample to the original Theorem 5.4. As explained in our rebuttal, we have corrected the error and replaced the theorem with a new universal lower bound, together with a matching algorithm, BudgetAlarm, establishing the exact deterministic consistency–robustness frontier.
We hope that this new result addresses your central concern regarding Pareto optimality and the substantive theoretical contribution of the paper.
We would greatly appreciate your reassessment in light of these revisions and would be happy to address any further concerns.
Thank you again for your time and careful consideration.
Revised Theorem 5.4 and the universal lower bound
Thank you for carefully reading the paper and for providing the counterexample.
The original Theorem 5.4. Yes, your fallback is valid in our model and has consistency 1 and robustness at most 3. Section 5.2 of the revised manuscript describes it, and Appendix A.2 proves the bound. In normalized units, OPT=1+∑gmin(g,1), where the sum runs over consecutive gaps and the leading 1 pays for the final ACK. The fallback matches the offline cost on every gap before the first misclassification. If a predicted short gap times out, the fallback pays 2 against an offline cost of 1. If a predicted long gap turns out to be short, it pays 1, which is at most one unit above twice the offline gap cost. The remaining gaps and the final ACK cost at most twice their offline contributions, so ALG≤2OPT+1≤3OPT.
This disproves the original Theorem 5.4, whose two-packet argument also omitted mandatory ACK costs.
BudgetAlarm and the revised Theorem 5.4. For each target consistency κ∈[1,2], the revised Theorem 5.4 gives the smallest possible robustness among deterministic algorithms with consistency at most κ. Our new algorithm, BudgetAlarm, attains this value, R⋆(κ)=1+2κ1+1+4κ. The optimal robustness is about 2.618 at perfect consistency and 2.380 at consistency 1.25.
For a candidate robustness R=1+s, the lower bound in Appendix A.3 tracks D, the cost of completed gaps minus R times their offline cost. Fixing every prediction to +∞ gives the prediction-free lower bound s≥1. If the input ends at the current arrival and the algorithm waits t before the final ACK, robustness requires D+1+t≤R, so t≤s−D.
Let b=s−1/s. Suppose D=b+u for some u>0. If D>s, ending the input already violates robustness. Otherwise the ACK delay satisfies t≤1/s−u. The adversary can then release the next packet just after that ACK, at a gap of t+ε<1. The new value of D is D+1−st−Rε≥b+(1+s)u−Rε. By choosing ε sufficiently small at each step, the adversary makes the excess above b grow geometrically until D>s. Thus any algorithm with robustness R must have D≤b at every arrival.
Now consider a first packet with a prediction of +∞. If it is the only packet, the prediction is correct, so consistency forces the first ACK delay to be at most κ−1. For κ<2, the adversary can release a second packet just after that ACK. Applying D≤b to this gap and taking ε to zero gives 1−s(κ−1)≤b, or κs2≥s+1. Solving this inequality yields R≥R⋆(κ). At κ=2, the prediction-free lower bound already gives R≥2.
To attain the bound, BudgetAlarm sets R=R⋆(κ) and uses the forecasts when D≤0. It sets a timeout of κ−1 for a predicted long gap and s for a predicted short gap. Either timer can increase D by at most b on one gap, so D stays at most b. When D>0, BudgetAlarm uses a timeout of 1/s, which prevents D from increasing and limits the final ACK cost to R−b. When D≤0, the final ACK costs at most R. In both cases, the total cost is at most ROPT. With perfect predictions, each gap costs at most κ times its offline cost. Since R≥κ, this keeps D≤0, and the final ACK costs κ.
Theorems 5.1 and 5.2 give AugmentedAlarm’s exact, continuous error-dependent ratio. Corollary 5.3 gives its consistency 1+λ and robustness 1+1/λ. Theorem 5.4 establishes BudgetAlarm’s Pareto optimality among all deterministic algorithms, including those with continuous or discontinuous error curves. At matched consistency κ=1.25, BudgetAlarm’s ratio jumps to about 2.380 just above normalized error 0.380. AugmentedAlarm gives a tighter guarantee just above that threshold and has robustness 5 under arbitrary errors. Appendix A.4 and Figure 3 compare the guarantees across error levels.