Search papers, labs, and topics across Lattice.
This paper investigates the pod-deployability problem in Kubernetes, focusing on how affinity and anti-affinity constraints affect pod placement. The authors establish that while pod-deployability is decidable in polynomial time without affinity constraints, introducing required affinity alongside anti-affinity escalates the problem's complexity to PSPACE-complete. Their findings reveal that even a single node with one scalar capacity can lead to PSPACE-completeness when required affinity is present, highlighting the intricate challenges in Kubernetes scheduling.
Introducing required affinity in Kubernetes scheduling transforms the pod-deployability problem into a PSPACE-complete challenge, exposing hidden complexities in resource management.
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.
