Contract Scheduling with Distributional and Multiple Advice
This work addresses real-time system design for interruptible capabilities, offering incremental advances by generalizing from single deterministic predictions to more realistic distributional and multiple advice settings.
The paper tackles contract scheduling by introducing learning-augmented settings where predictions are given as probability distributions or multiple possible times, designing schedules that are optimal with accurate predictions and guarantee best worst-case performance otherwise, with experimental results confirming theoretical improvements.
Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice.