Multi-Level Aggregation with Delays and Stochastic Arrivals

Abstract

In online Multi-Level Aggregation (MLA) with delays, the input is an edge-weighted rooted tree $T$ and a sequence of requests arriving at its vertices (with each vertex representing an independent agent) that need to be served in an online manner. Each request $r$ is characterized by two parameters: its arrival time $t(r)$ and its location $l(r)$ (a vertex). Once $r$ arrives, we can either serve it immediately or postpone this action until any time later. We can serve several pending requests at the same time, paying a service cost equal to the weight of the subtree that contains the locations of all the requests served and the root of $T$. Postponing the service of a request $r$ to time $t$ generates an additional delay cost of $t - t(r)$. The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The MLA problem is a generalization of several well-studied problems, including the TCP Acknowledgment (depth 1), Joint Replenishment (depth 2), and Multi-Level Message Aggregation (arbitrary depth). This problem has only been studied in an adversarial model thus far, and the current best algorithm for this problem achieves a competitive ratio of $O(d^2)$, where $d$ denotes the depth of the tree. We study a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm that achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant.