- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies randomized online algorithms subject to a worst-realization performance guarantee, termed dependability. It derives exact tradeoffs between dependability and expected competitive ratio for online bidding and line search. For TCP acknowledgment, it provides an upper bound and a nontrivial lower bound, extending the analysis to a setting where algorithms adapt their decisions to arriving requests.
Critical strengths
-
The exact frontiers are substantive theoretical contributions. The results characterize what randomization can achieve while retaining a deterministic-style worst-realization guarantee. Matching upper and lower bounds for two canonical problems provide a complete answer rather than merely another competitive algorithm.
-
The step-ratio lemma supplies a clear structural insight. It explains how dependability restricts the growth of feasible bidding or search sequences and why geometric strategies attain the optimal tradeoff. Reusing the lemma across online bidding and line search makes the contribution more coherent and potentially reusable.
-
The TCP lower-bound argument addresses a genuine additional difficulty. The penalizing-suffix construction derives constraints on dependable deterministic algorithms despite their ability to adapt to packet arrivals. These constraints then support a fixed adversarial distribution for the randomized lower bound; this is more substantial than directly transferring the non-adaptive search analysis.
Critical weaknesses
-
The most distinctive extension remains incomplete. For TCP acknowledgment, the upper and lower bounds do not coincide, and the new lower bound improves on the unconstrained randomized bound only over a limited dependability range. Thus, the paper characterizes the adaptive setting less completely than the two search problems.
-
The algorithmic contribution is narrower than the collection of results might initially suggest. The constructive strategies primarily parameterize or modify established algorithms. The strongest novelty therefore lies in the lower-bound techniques. A sharper explanation of which proof ingredients are specific to these problems and which support a broader theory would strengthen the paper’s significance.
Questions for authors
-
Is the proposed TCP distribution optimal within the family of fixed-threshold algorithms, or is it only a feasible construction achieving the stated bound?
-
Does the remaining TCP gap primarily reflect the restriction to two-burst lower-bound instances, or is there also evidence that the upper-bound algorithm could be improved?
2 comments
Thanks a lot for the detailed rebuttal message, which addresses most of my concerns. I'll keep my original positive score.
Response to Reviewer 38UK
We thank the reviewer for the insightful comments. We hope the below answers adequately address your concerns.
Weakness W1 (bounds gap for TCP acknowledgment)
We agree that the adaptive setting is characterized less completely than the two search problems. As we explain in our responses to Reviewers 8uVB and 48eW, we believe that neither of our two bounds for TCP acknowledgment is tight, and that adaptivity is the reason in both cases. The adversary can use instances with more bursts, and the algorithm can carry its unused budget over to later rounds. Our paper is the first to study tail constraints for an adaptive problem. It provides concrete tools for this setting (the post-ack budget and the penalizing suffix) that could be useful in further work on related problems.
Weakness W2 (contribution)
We agree that the lower bounds are the most novel parts of the paper.
In our view, they are not only interesting results by themselves, but our intention was also to extract certain properties of algorithms constrained by the tail bounds that may generalize to a wider group of problems. One of them is the step ratio lemma (Lemma 9), which shows that if the prefix sums of bids satisfy the tail constraint, then the sum of ratios of consecutive bids is appropriately lower-bounded. The other is the penalizing suffix lemma (Lemma 27), where the adversary repeatedly forces the algorithm to pay a fixed cost while the optimal cost grows slowly, and the budget is upper-bounded by an affine map with an unstable fixed point.
We will try to make these tools more self-contained and ready to be reused in other problems.
Question Q1 (conditional optimality of proposed TCP distribution)
We conjecture that the presented algorithm is optimal not only in the family of fixed-threshold algorithms, but even in the class of algorithms defined in Remark 19 (an algorithm that: (i) samples a parameter z1∈[r,1] at the beginning of its execution, (ii) after the i-th acknowledgment, chooses a new parameter zi+1∈[r,1] and uses it to determine the time of the next acknowledgment). We also kindly refer you to our answer for Questions 1 and 2 of Reviewer 48eW. We will state this conjecture formally in our paper.
Question Q2 (tightness of TCP bounds)
The lower bound can be improved, and we conjecture that the upper bound can be improved as well. We include here a part of the answer to the question of Reviewer 8uVB:
On the one hand, the lower bound can be improved by using instances with more than two bursts, as Lemma 22 provides constraints for any number of bursts. However, the improvement that we obtained this way was minor while it made the analysis substantially more complicated, so we decided to present the two-burst construction only.
On the other hand, we conjecture that the upper bound is not tight either. Dependability constrains the total cost of the whole execution, while our algorithm satisfies it separately in each round. On instances where the algorithm pays less than the constraint allows in initial rounds, it could keep the unused budget and spend it in later rounds by choosing thresholds smaller than r. We will mention both observations as interesting future directions in the conclusion.