Reference. Weighted NetKAT: A Programming Language for Quantitative Network Verification

We introduce weighted NetKAT, a domain-specific language for modeling and verifying quantitative quantitative network properties. The language is parametric on a semiring , enabling the treatment of a wide range of quantities in a uniform way. We provide a denotational semantics and an equivalent operational semantics, the latter based on a novel model of weighted NetKAT automata ( WNKA ) capturing the stateful behavior of our language. With WNKA , we obtain a class of generic decision procedures for reasoning about quantitative safety and reachability in a fully automatic way, even in the presence of possibly unbounded iteration. We demonstrate the applicability of our framework in a case study using Internet2’s Abilene network as the underlying topology.

Cite

Cite as @suarezacevedo-2026-weighted (helia, typst) · \cite{suarezacevedo-2026-weighted} (LaTeX)
BibTeX
bibtex · 1 line
@article{suarezacevedo-2026-weighted, title={Weighted NetKAT: A Programming Language for Quantitative Network Verification}, volume={10}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3808318}, DOI={10.1145/3808318}, number={PLDI}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Suárez Acevedo, Emmanuel and Ferreira, Tiago and Batz, Kevin and Bøving, Oliver and Foster, Nate and Silva, Alexandra}, year={2026}, month=June, pages={1788–1811} }
hayagriva YAML (typst)
yaml · 20 lines
suarezacevedo-2026-weighted:
  type: article
  title: 'Weighted NetKAT: A Programming Language for Quantitative Network Verification'
  author:
  - Acevedo, Emmanuel Suárez
  - Ferreira, Tiago
  - Batz, Kevin
  - Bøving, Oliver
  - Foster, Nate
  - Silva, Alexandra
  date: 2026-06
  page-range: 1788-1811
  serial-number:
    doi: 10.1145/3808318
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: PLDI
    volume: 10
Cited by (2)

A Fast Quantitative Analyzer for NetKAT lu-2026-a

When designing a network, engineers must navigate trade-offs (e.g., one topology offers more aggregate bandwidth, another lower latency or better resilience) that demand reasoning about quantitative properties. We present a fast analyzer for quantitative network properties based on weighted NetKAT (wNetKAT), a domain-specific language that provides a semantic foundation for quantitative reasoning by modeling network behavior using weights drawn from a semiring. At the core of our development is the design of a symbolic data structure – weighted symbolic packet programs (wSPPs) – that compactly represent the semantics of weighted policies, for which a direct implementation would be intractable. We show how to compute all policy constructs symbolically; unsurprisingly, the crux is Kleene star, for which we design a tailored algorithm. We further develop trace-carrying Pareto semirings, which compute multi-objective frontiers together with the network paths that realize them. We formalize the development in Lean and provide an optimized Rust implementation. Being parametric on a semiring, our implementation covers both classical and quantitative analyses: we show that it is competitive with KATch, a heavily optimized Boolean-reachability verifier, and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies shows the framework supports multi-objective design-time analysis.
arXiv

SMT-Based Active Learning of Weighted Automata ferreira-2026-smt

We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/𝘓⋆-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.
PDF · DOI · arXiv · pldb
Cites 40 works (6 here)
With notes (6)

Active Learning of Symbolic NetKAT Automata moeller-2025-active

NetKAT is a domain-specific programming language and logic that has been successfully used to specify and verify the behavior of packet-switched networks. This paper develops techniques for automatically learning NetKAT models of unknown networks using active learning. Prior work has explored active learning for a wide range of automata (e.g., deterministic, register, Büchi, timed etc.) and also developed applications, such as validating implementations of network protocols. We present algorithms for learning different types of NetKAT automata, including symbolic automata proposed in recent work. We prove the soundness of these algorithms, build a prototype implementation, and evaluate it on a standard benchmark. Our results highlight the applicability of symbolic NetKAT learning for realistic network configurations and topologies.
PDF · DOI · arXiv · pldb

Weighted GKAT: Completeness and Complexity vankoevering-2025-weighted

We propose Weighted Guarded Kleene Algebra with Tests (wGKAT), an uninterpreted weighted programming language equipped with branching, conditionals, and loops. We provide an operational semantics for wGKAT using a variant of weighted automata and introduce a sound and complete axiomatization. We also provide a polynomial time decision procedure for bisimulation equivalence.
DOI · arXiv

Guarded Kleene algebra with tests: verification of uninterpreted programs in nearly linear time smolka-2019-guarded

Guarded Kleene Algebra with Tests (GKAT) is a variation on Kleene Algebra with Tests (KAT) that arises by restricting the union (+) and iteration (*) operations from KAT to predicate-guarded versions. We develop the (co)algebraic theory of GKAT and show how it can be efficiently used to reason about imperative programs. In contrast to KAT, whose equational theory is PSPACE-complete, we show that the equational theory of GKAT is (almost) linear time. We also provide a full Kleene theorem and prove completeness for an analogue of Salomaa’s axiomatization of Kleene Algebra.
PDF · DOI · arXiv · pldb

Probabilistic NetKAT foster-2016-probabilistic

PDF · DOI · pldb

Algebra-coalgebra duality in brzozowski’s minimization algorithm bonchi-2014-algebra

We give a new presentation of Brzozowski’s algorithm to minimize finite automata using elementary facts from universal algebra and coalgebra and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal language equivalent automata from Moore nondeterministic and weighted automata.
DOI

Kleene algebra with tests kozen1997kleene

We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program with at most one while loop. The proof illustrates the use of Kleene algebra with tests and commutativity conditions in program equivalence proofs.
PDF · DOI · pldb
External (34)
suarezacevedo-2026-weighted reference entries/refs/suarezacevedo-2026-weighted/suarezacevedo-2026-weighted.hel