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

Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro

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 o…