CS Paper Radar

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete

Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

cs.CC cs.DC ·submitted 2026-08-20 09:19 UTC · v1

Abstract

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimizing API Gateway Placement in Multi-Cloud Kubernetes

cs.DC ·2026-08-27 ·Vinoth Punniyamoorthy, Murali Shankar Dulam, Aswathnarayan Muthukrishnan Kirubakaran, Akshay Deshpande, Nachiappan Chockalingam +3 more
theory similarity 0.62
Abstract

The use of API gateways within geographically distributed multi-cloud Kubernetes clusters poses a tradeoff between infrastructure cost, computational resources, and network latencies. We present an optimization formulation that addresses API gateway placement as a capacitated facility location problem that jointly determines which candidate clusters to activate, how many gateway replicas to deploy, and how regional traffic should be distributed across the selected clusters. The formulation imposes an upper bound on estimated client-to-cluster network round-trip latency, excluding gateway processing, queuing, and backendservice latency, and incorporates a utilization headroom factor for gateway replica capacity. We present both a mixed-integer linear programming (MILP) formulation and a constructive greedy heuristic that ranks candidates according to incremental cost, comprising cluster-activation and marginal replica costs, per unit of assignable capacity while explicitly accounting for already committed load. Both formulations are applied to deterministic, seed-controlled, geography-based synthetic instances. For each problem size, 30 instances are generated with random seeds to analyze their performance. The greedy algorithm achieves an optimality gap of 3.2% to 4.7% to the MILP optimal solution, with a maximum observed gap of 25.0% for one particular instance, and a speedup of approximately 660x to 3,490x for 3 to 12 candidate clusters. In a canonical 10-candidate, 10-demand region instance, MILP-optimal deployment saves 24.2% in terms of monthly cost compared to the full-replication baseline. On the other hand, selecting the single cheapest candidate yields savings of 24.8% compared to the MILP optimum but does not satisfy the latency requirement for 3 out of 10 demand regions.

0.20

KubeCap: A Framework for Capability Minimization in Kubernetes via Static Analysis and LLM-Assisted Rule Inference

cs.CR cs.SE ·2026-08-27 ·Yuhao Liu, Yingnan Zhou, Weijie Liu, Yan Jia, Zheli Liu
publishedcode/data similarity 0.62
Abstract · 12 pages, 5 figures, accepted to the 37th IEEE International Symposium on Software Reliability Engineering (ISSRE 2026)

As the most widely used container orchestration platform, Kubernetes provides flexible privilege configuration by allowing developers to manage Linux capabilities via manifest files. However, developers rely on default settings or coarse-grained security contexts in practice, violating the principle of least privilege and enlarging the attack surface of containerized workloads. Existing studies either detect vulnerable patterns in Kubernetes manifests or infer required capabilities for standalone Linux programs, but they do not directly address capability minimization in Kubernetes. To bridge this gap, we first conduct an empirical study on three open-source datasets, revealing that 74.67% of projects lack capability configurations. Motivated by our observations, we propose KubeCap, a framework for Kubernetes capability minimization. KubeCap translates deployment specifications into deterministic manifests, locates container entrypoints, performs reachability-guided system call analysis, and leverages LLM-assisted rule specification to derive syscall--parameter--capability relations from Linux kernel code. Based on these results, KubeCap infers the minimal capability set required by each workload and automatically generates repaired manifests. Evaluation on 10 representative Go-based Kubernetes projects shows an average capability reduction rate of 54.97%, outperforming rapid type analysis and class hierarchy analysis baselines while maintaining practical analysis cost. These results demonstrate KubeCap's effectiveness in enforcing least privilege in Kubernetes.

0.56

Fleet-Scale Pod Deployment with VPC-Native Networking in Managed Kubernetes

cs.NI cs.DC ·2026-08-23 ·Sri Saran Balaji Vellore Rajakumar, Jayanth Varavani, Murat Parlakisik, Pavani Panakanti
similarity 0.59
Abstract

Managed Kubernetes pod deployment is often presented as a choice between VPC-native and overlay networking. Public EKS documentation describes prefix-mode capacity and configuration, while prior CNI studies primarily measure steady-state throughput and latency. This paper presents an operational measurement study of fleet-scale pod deployment across three VPC-native modes on Amazon EKS: individual secondary-IP allocation, ENI preallocation, and IPv4 prefix delegation, using Cilium and Calico as overlay baselines. We compare representative mode-specific warm-pool settings, so the results describe combined operating points. At 400 nodes, the tested three-address secondary-IP warm pool required 7,403 seconds to place 80,000 pods. With the tested ENI-preallocation and prefix-delegation settings, the same workload completed in approximately 495 seconds, moving address provisioning off the pod-creation critical path. In the reported 400-node runs, prefix delegation achieved approximately 162 pods/s, within the same observed range as the fastest overlay baseline and ENI-preallocation runs, while requiring fewer successful EC2 provisioning calls per pod than individual-IP allocation by allocating addresses in /28 blocks. Because each /28 contains 16 addresses and occupies one IPv4 slot, an interface with 30 slots carries 29 prefixes, representing up to 464 potential pod addresses, compared with approximately 30 IPv4 slots per ENI for individual-IP allocation when kubelet and CNI limits are configured accordingly. Prefix delegation also has lower documented network-address usage and retains direct VPC reachability and flow-log visibility but the trade-off is that /28 allocations require contiguous subnet space.

0.28

Budgeted Admission from Timestamped Capacity Records in Shared Clusters

cs.DC math.PR ·2026-10-20 ·Andrew Bond, Syed Izhan Khilji
similarity 0.54
Abstract

A cluster admission gate can receive a capacity record that no longer matches current schedulability. We study one exogenous binary schedulability unit under a bound on the joint probability of admission and unavailability. For a symmetric Markov state, we derive the stationary admission frontier for a fixed observation delay and apply finite likelihood allocation to a delay-tagged delivered record. A one-sided exact binomial endpoint calibrates each fitted policy, and exact enumeration confirms the per-policy confidence target in every tested parameter cell. A separate deterministic guard charges every unresolved admission against the realized allowance and bounds unavailable-state admissions at every prefix under truthful outcome feedback. An executable admission procedure composes the allocation and guard. The controlled system binds source sampling, NATS delivery, randomized admission, Kubernetes objects, and API-derived outcomes in one append-only record. Independent audit finds no missing event, identity mismatch, or state mismatch in the completed functional block. A separate CPU request-accounting check preserves Job and Pod identity across an unschedulable-to-complete transition.

0.27

Why Kubernetes Cannot Contain a Full Lazy-Pulling Cache: Two Impossibility Results and a Bounded, Honest Design for Model Serving

cs.DC cs.OScs.PF ·2026-11-09 ·Georgii Kliukovkin
code/data similarity 0.54
Abstract · 10 pages, 2 figures. Under review at IEEE Access. Data, protocols, and harness: https://github.com/kliukovkin/lazy-model-delivery-study

Lazy container-image pulling makes cold starts of autoscaled model-serving fleets on Kubernetes nearly independent of model size, but it moves the model's bytes into a node-level cache that the platform neither bounds nor accounts for. This article establishes, by experiment, two impossibility results for that cache. A monitoring-side remedy cannot catch its failure: a sentinel readiness probe stays green while 272 of 280 files are unreadable. A platform-side remedy cannot contain it: kubelet, given full disk-pressure visibility, frees 0 bytes and evicts 26 bystander pods, because its reclamation actuator is keyed to an accounting that does not know the cache exists. The article then eliminates the failure class inside the component that owns the bytes, with no change to kubelet or the container runtime interface, by two design rules: a byte budget whose pressure signal is keyed to filesystem truth, so that a never-blocking, lossy accounting still enforces a hard bound (held against about 301,000 dropped updates), and pass-through semantics under which a failed cache write never becomes a failed read, with the coupling traced to a single io.MultiWriter. Across six pre-specified campaigns on AWS, upstream stargz-snapshotter fails 273 of 280 model files at 90% cache pre-fill; the proposed system reads all 150.3 GB with zero errors at +18.5% completion cost and holds the budget under a live read, co-tenancy, and a three-node fleet. A source audit shows the missing bound generalizes to SOCI and Nydus. The implementation is open source and has been proposed upstream.

0.27

Domain-Knowledge Driven Configuration Tuning of Kubernetes Workloads

cs.SE ·2026-10-12 ·Federico Imberti, Luca Cavagnis, Stefano Cereda, Giovanni Gibilisco, Claudio Menghi
similarity 0.54
Abstract

Industrial software applications often require engineers to tune the software deployment platform. Configuration tuning identifies valuable configurations that minimize costs while ensuring the application performance. However, finding these configurations is difficult. The number of tunable configuration parameters in industrial applications is large, and engineers cannot assess different configurations in production because users may experience performance degradation. This work targets Kubernetes: A system for automating the deployment, scaling, and management of containerized applications. This paper proposes a domain-knowledge-driven solution for finding configurations of industrial applications in a practical time. The solution relies on a catalog of constraints encountered by domain experts in similar applications. Depending on the problem under analysis, engineers can customize the optimization problem by selecting the relevant constraints from the catalog for the application at hand. We rely on two alternative solvers to find an optimal configuration: The first is based on heuristics, while the second reuses existing optimization-based solutions. We implemented our solution within an industrial tool from a software company specializing in performance engineering and optimization. We compare our solution to a baseline, considering a set of predefined configuration values provided by engineers. Our results confirm the effectiveness of our solution: Compared to the baseline, the heuristic-based and optimization-based solutions provide significant average savings of 11591 USD/mo and 15874 USD/mo per Kubernetes, respectively, accounting for 24.03% and 32.90% of the costs, in practical time (0.71 seconds per extraction for the heuristic-based and 45.54 seconds per extraction for the optimization-based solution).

0.29

ScaleBench: An Extensible and Reproducible Experimental Platform for Kubernetes Autoscaling Research

cs.DC ·2026-11-18 ·Ze Wang, Sajid Alam, Amjad Ullah
similarity 0.52
Abstract · Accepted for publication in the 1st Workshop, titled ContinuumOps: DevOps for the Edge-Cloud Continuum, which was co-located with the 24th I…

Autoscaling enables cloud-native applications to meet their SLOs by dynamically adjusting computational resources at runtime. Recent research has explored a broad range of advanced autoscaling approaches, including rule-based, optimisation-based, and machine learning-based techniques, to address the limitations of traditional resource management strategies in cloud-native environments. Despite significant advances, a considerable gap remains between academic innovations and their practical adoption in real-world environments. For instance, Kubernetes deployments commonly rely on the reactive, CPU-based Horizontal Pod Autoscaler, limiting the adoption of more advanced autoscaling approaches. Recent studies have investigated challenges such as autoscaler configuration and reproducible performance evaluation; however, the practical deployment, integration complexity, and operational overhead of research-based autoscalers in Kubernetes environments have received limited attention. To address this gap, we present ScaleBench, a native Kubernetes experimental platform to enable extensible and reproducible evaluation of autoscaling solutions. Unlike existing approaches, ScaleBench integrates autoscalers as native Kubernetes components, allowing researchers to assess not only scaling performance but also deployment characteristics and integration requirements within realistic cloud-native environments. We demonstrate the effectiveness of ScaleBench by evaluating multiple autoscaling approaches through a case study. The results highlight its capability to support systematic, repeatable, and practical assessment of Kubernetes autoscaling approaches.

0.23

Kirin: Cloud-native WebAssembly Service Orchestration

cs.DC ·2026-09-30 ·Joshua Bauer, Sebastian Werner, Maria C. Borges
published similarity 0.52
Abstract · Accepted at IC2E 2026

Modern cloud computing infrastructure relies heavily on virtualization to provide workload isolation and resource efficiency. While containers have become the dominant deployment primitive due to their fast orchestration compared to traditional virtual machines, they still introduce non-trivial overhead. WebAssembly (Wasm) has emerged as an alternative isolation technology, offering a lightweight execution model. Because of compatibility limitations, WebAssembly has mainly been applied to Function-as-a-Service (FaaS) and Edge Computing scenarios, where it has attracted growing research interest. However, recent advances in the WebAssembly ecosystem have significantly matured the technology, raising the question of whether it can serve as a viable replacement for containers in cloud-native workloads. In this paper, we present Kirin, an orchestrator for cloud-native WebAssembly services. It supports core orchestration responsibilities, including resource scheduling, lifecycle management, scaling, and request routing. We evaluate Kirin against container-based deployments for several service workloads and demonstrate promising results, particularly in service lifecycle management. Simultaneously, we confirm known limitations in CPU-intensive workloads. However, for typical service workloads, Kirin demonstrates competitive performance, suggesting that WebAssembly is a viable candidate for broader adoption as a cloud-native deployment technology.

0.17