Metraipolis › archive › dc_edcd911ee620

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete — arXiv:2608.19822

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.19822
License (as archived): CC0-1.0
Archived: 2026-10-18T11:40:51.084Z
SHA-256 of the archived text: 88c129d0ce2f0cacdc92df25784a4cbdc54473658e12fc7b2bc4bdb5c65cdc9a
Stable URL of this page: https://metraipolis.com/documento/dc_edcd911ee620

How to cite

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete — arXiv:2608.19822 — arXiv (en), https://arxiv.org/abs/2608.19822 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_edcd911ee620 (Metraipolis archive dc_edcd911ee620, sha256 88c129d0ce2f0cacdc92df25784a4cbdc54473658e12fc7b2bc4bdb5c65cdc9a)

BibTeX

@misc{dcedcd911ee620,
  title = {Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete — arXiv:2608.19822},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.19822},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_edcd911ee620; sha256 88c129d0ce2f0cacdc92df25784a4cbdc54473658e12fc7b2bc4bdb5c65cdc9a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.19822. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-21 in cs.DC).
Categorie arXiv: Computational Complexity (cs.CC) ; Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2608.19822 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T11:38:59.520Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-08-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).