Introduction
In modern distributed systems, requests often arrive asynchronously and unpredictably. Whether it is a ride-hailing platform matching passengers, an ad-server grouping video requests, or an IoT gateway aggregating sensor data, system designers face a fundamental tension: immediate processing incurs high overhead, while delayed processing to form larger batches increases latency. This paper presents a principled framework for dynamic batching, optimizing the balance between the cost of delay and the "economies of scale" inherent in bulk processing.
Problem Formulation
The core challenge of dynamic batching lies in the online nature of arrivals. A system cannot know when the next request will appear. Traditional strategies—such as waiting for a fixed number of requests or a fixed duration—often fail under variable arrival rates. If a system waits for a fixed size of 10, the 10th request might not arrive for hours; if it waits for a fixed time, it might process inefficiently small batches during low-traffic periods.
The authors model the processing cost using a submodular set function. This mathematical choice captures the diminishing marginal cost of adding requests to a batch: as a batch grows, the incremental cost of adding one more request decreases. The objective is to minimize the total cost, defined as the sum of all processing costs and the cumulative waiting time of all requests.
Methodology
The Offline Optimal (OSP)
To establish a benchmark, the authors first solve the offline version of the problem where all arrival times are known in advance. They demonstrate that the Optimal Scheduling Problem (OSP) can be reduced to finding the shortest path in a weighted Directed Acyclic Graph (DAG). In this graph, nodes represent individual arrivals, and edges represent the cost of batching a specific sequence of arrivals. This reduction allows for an exact solution in $O(n^2)$ time, providing a baseline for evaluating online strategies.
The Online Algorithm: WaitTillAlpha (WTA)
For real-world scenarios where the future is unknown, the authors introduce WaitTillAlpha (WTA). This algorithm is simple yet robust: it tracks the total waiting time accumulated by all requests currently in the queue. Once this "waiting pain" reaches a specific threshold—defined as a multiple ($\alpha$) of the cost to process the current batch—the system triggers processing. This approach essentially treats waiting time as a budget used to "buy" more efficient processing costs.
Theoretical Analysis
Using a potential function argument, the researchers prove that WTA is 3-competitive against an omniscient adversary for a wide range of submodular cost functions when $\alpha = 1/2$. This means that regardless of the arrival pattern, the online algorithm's total cost is guaranteed to be no more than three times the cost of the optimal offline schedule. The performance is further influenced by the "curvature" ($\Gamma$) of the cost function, which measures the strength of the economies of scale. The authors established a lower bound of $1/\Gamma$ for the competitive ratio.
Empirical Evaluation
The framework was tested using both synthetic simulations (Poisson processes) and real-world data. The real-world dataset comprised customer arrival patterns at three different banks over a four-week period, capturing the natural "burstiness" of human activity.
Key findings include:
- Practical Efficiency: While the theoretical upper bound is 3, WTA typically performed within 1.3x of the offline optimum on real-world data, suggesting the worst-case scenarios are rare in practice.
- Robustness: The algorithm maintained high performance even during inhomogeneous arrival rates (e.g., peak hours vs. quiet periods), proving it does not rely on steady-state assumptions or prior knowledge of arrival distributions.
Conclusion and Future Directions
WaitTillAlpha provides a generalized, provably efficient solution for dynamic batching across various domains, from cloud computing to logistics. However, some avenues remain for future exploration. The current model treats waiting as a linear cost rather than a hard deadline; extending the framework to accommodate strict latency constraints would benefit real-time communication systems. Additionally, while the current study focuses on batch size, future work could explore multi-dimensional features where processing costs depend on the specific attributes of the requests within a batch.
Summary updated