Nate Foster


Cantor Meets Scott: Semantic Foundations for Probabilistic Networks

November 30, 2016 at 3:30pm
CSE 305


The emergence of software-defined networking (SDN) has led to the development of a number of domain-specific programming languages and reasoning tools for networks. But there is still a large gap between the programming models offered by these languages and the realities of modern networks. In particular, most existing languages are based on deterministic functions, which makes it impossible to encode probabilistic behaviors. ProbNetKAT is a high-level network programming language that comes equipped with a random choice operator that can be used to express a variety of probabilistic behaviors. I will describe the design of ProbNetKAT, present a semantics using Markov Kernels, and show how to use the language to reason about quantitative properties such as congestion, latency, and fault tolerance.

ProbNetKAT is joint work with Dexter Kozen (Cornell), Praveen Kumar (Cornell), Konstantinos Mamouras (UPenn), Mark Reitblatt (Facebook), Alexandra Silva (UCL), and Steffen Smolka (Cornell).


Nate Foster is an Associate Professor of Computer Science at Cornell University and a Visiting Researcher at Barefoot Networks. The goal of his research is to develop languages and tools that make it easy for programmers to build secure and reliable systems. His current work focuses on the design and implementation of languages for programming software-defined networks. In the past he has also worked on bidirectional languages (also known as “lenses”), database query languages, data provenance, type systems, formal semantics, and mechanized proof. He received a PhD in Computer Science from the University of Pennsylvania, an MPhil in History and Philosophy of Science from Cambridge University, and a BA in Computer Science from Williams College (where he was advised by Pomona Professor Kim Bruce). His awards include an NSF CAREER Award, a Sloan Research Fellowship, a Most Influential POPL Paper Award, a Tien ‘72 Teaching Award, a Cornell Engineering Research Excellence Award, and the Morris and Dorothy Rubinoff Dissertation Award.