POPL 2017
Sun 15 - Sat 21 January 2017
Thu 19 Jan 2017 16:55 - 17:20 at Amphitheater 44 - Semantic Foundations Chair(s): Lars Birkedal

ProbNetKAT is a probabilistic extension of NetKAT with a denotational semantics based on Markov kernels. The language is expressive enough to generate continuous distributions, which raises the question of how to effectively compute in the language. This paper gives an alternative characterization of ProbNetKAT’s semantics using domain theory, which provides the foundations needed to build a practical implementation. The new semantics demonstrates that it is possible to analyze ProbNetKAT programs precisely using approximations of fixpoints and distributions with finite support. We develop an implementation and show how to solve a variety of practical problems including characterizing the expected performance of traffic engineering schemes based on randomized routing and reasoning probabilistically about properties such as loop freedom.

slides (2017-01-POPL.pdf)4.13MiB

Thu 19 Jan
Times are displayed in time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

16:30 - 17:20
Semantic FoundationsPOPL at Amphitheater 44
Chair(s): Lars BirkedalAarhus University
A Semantic Account of Metric Preservation
Arthur Azevedo de AmorimUniversity of Pennsylvania, USA, Ikram CheriguiENS Paris, Marco GaboardiSUNY Buffalo, USA, Justin Hsu, Shin-ya KatsumataKyoto University
Cantor Meets Scott: Semantic Foundations for Probabilistic Networks
Steffen SmolkaCornell University, Praveen KumarCornell University, Nate FosterCornell University, Dexter KozenCornell University, Alexandra SilvaUniversity College London
DOI File Attached