C-PCP: Correlation-Aware Proportional Critical Path Scheduling for Input-Sensitive Serverless Workflows

Abstract

Serverless computing is a cost-effective, on-demand paradigm for deploying application workflows, but it faces a key challenge in efficient resource allocation. Platforms must provision resources that satisfy Service Level Objectives (SLOs) while minimizing operational cost. In real workflows, execution time depends on input size, but most approaches are input-agnostic, causing SLO violations for large inputs and overprovisioning for small ones. Recent input-aware schedulers still rely on static averages along the critical path, failing to capture dynamic, input-dependent dataflow across stages. In this work, we propose a Correlation-Aware Proportional Critical Path (C-PCP) method that employs a dynamic, input-aware weighting model derived from online profiling data. A correlation matrix captures statistical dependencies between the input and output sizes of sequential functions, enabling dynamic critical path computation, more accurate sub-SLO allocation, and improved resource profile assignment. Additionally, we develop a dynamic programming based theoretical lower bound to provide a rigorous performance benchmark. For experimental validation, workflow task profiling data is collected from execution traces on a Knative-based testbed deployed over Kubernetes, ensuring realistic modeling of workflow behavior. We evaluate the proposed approach on diverse real-world and synthetic workflows, demonstrating consistent improvements over state-of-the-art methods in both SLO satisfaction and cost efficiency.