Learning-Augmented Online Acknowledgment with Worst-Case Latency Guarantees

We study the online acknowledgment problem under a maximum-latency objective, which captures tail latency and min–max fairness in systems where delayed responses may block downstream progress. An online algorithm observes packet arrivals over time and must decide when to issue acknowledgments, trading off acknowledgment overhead against the maximum delay among the packets covered by each acknowledgment. We consider this problem in a learning-augmented setting, where the algorithm receives incremental (possibly erroneous) predictions of the next arrival time. We introduce a deterministic, parameterized algorithm, AugmentedAlarm$(\lambda )$, whose performance depends explicitly on the prediction error and a trust parameter $\lambda$. We give a tight, error-dependent characterization of its competitive ratio: it is $(1+\lambda )$-competitive when predictions are perfect (consistency), $(1+1/\lambda )$-competitive under arbitrary error (robustness), and exhibits smooth, graceful degradation as prediction accuracy deteriorates. We prove matching upper and lower bounds, showing that this consistency–robustness tradeoff is Pareto-optimal: no deterministic online algorithm can simultaneously achieve better consistency and robustness. We further show that weaker prediction mechanisms, such as statistical information, are insufficient to achieve near-optimal performance, even when they are error-free. Finally, we complement our theoretical results with experiments on synthetic and real-world packet traces, confirming the predicted smooth dependence on prediction error and the practical benefits of learning-augmented strategies.