Publications

2023

• Formal Abstractions for Packet Scheduling
  Anshuman Mohan, Yunhe Liu, Nate Foster, Tobias Kappé, and Dexter Kozen.
  OOPSLA 2023
  🏆 Distinguished paper award
  PDF
• P4Testgen: An Extensible Test Oracle For P4-16
  Fabian Ruffy, Jed Liu, Prathima Kotikalapudi, Vojtech Havel, Hanneli Tavante, Rob Sherwood, Vladyslav Dubina, Volodymyr Peschanenko, Anirudh Sivaraman, and Nate Foster.
  SIGCOMM 2023
  PDF
• Hydra: Effective Runtime Network Verification
  Sundararajan Renganathan, Benny Rubin, Hyojoon Kim, Pier Luigi Ventre, Carmelo Cascone, Daniele Moro, Charles Chan, Nick McKeown, and Nate Foster.
  SIGCOMM 2023
  PDF
• P4Cub: A Little Language for Big Routers
  Rudy Peterson, Eric Campbell, John Chen, Natalie Isak, Calvin Shyu, Ryan Doenges, Parisa Ataei, and Nate Foster.
  CPP 2023
  PDF

2022

• Causal Network Telemetry
  Yunhe Liu, Nate Foster, and Fred Schneider.
  EuroP4 2022
  PDF
• A Programming Language for Future Interests
  Shrutarshi Basi, Nate Foster, James Grimmelman, James Grimmelman, Shan Parikh, and Ryan Richardson.
  YJoLT 2022
  PDF
• Leapfrog: Certified Equivalence for Protocol Parsers
  Ryan Donges, Tobias Kappé, John Sarracino, Nate Foster, and Greg Morrisett.
  PLDI 2022
  PDF
• Dependently-Typed Data Plane Programming
  Matthias Eichholz, Eric Campbell, Matthias Krebs, Nate Foster, and Mira Mezini.
  POPL 2022
  PDF

2021

• Avenir: Managing Data Plane Diversity with Control Plane Synthesis
  Eric Hayden Campbell, William T. Hallahan, Priya Srikumar, Carmelo Cascone, Jed Liu, Vignesh Ramamurthy, Hossein Hojjat, Ruzica Piskac, Robert Soulé, and Nate Foster.
  USENIX NSDI 2021
  PDF Code
• Petr4: Formal Foundations for P4 Data Planes
  Ryan Doenges, Mina Tahmasbi Arashloo, Santiago Bautista, Alexander Chang, Newton Ni, Samwise Parkinson, Rudy Peterson, Alaia Solko-Breslin, Amanda Xu, and Nate Foster.
  PACM (POPL) 2021
  PDF Code

2020

• Using Deep Programmability to Put Network Owners in Control
  Nate Foster, Nick McKeown, Jennifer Rexford, Guru Parulkar, Larry Peterson, and Oguz Sunay.
  SIGCOMM CCR 2020
  PDF
• Forwarding and Routing with Packet Subscriptions
  Theo Jepsen, Ali Fattaholmanan, Masoud Moshref, Nate Foster, Antonio Carzaniga, and Robert Soule.
  CoNEXT 2020
  🏆 Best paper award
  PDF
• Composing Dataplane Programs with μP4
  Hardik Soni, Myriana Rifai, Praveen Kumar, Ryan Doenges, and Nate Foster.
  SIGCOMM 2020
  PDF
• Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time
  Steffen Smolka, Nate Foster, Justin Hsu, Tobias Kappé, Dexter Kozen, and Alexandra Silva.
  PACMPL (POPL) 2020
  🏆 Distinguished paper award
  PDF

2019

• Proof Carrying Network Code
  Christian Skalka, John Ring, David Darias, Minseok Kwon, Sahil Gupta, Kyle Diller, Steffen Smolka, and Nate Foster.
  CCS 2019
  PDF
• Ancile: Enhancing Privacy for Ubiquitous Computing with Use-Based Privacy
  Eugene Bagdasaryan, Griffin Berlstein, Jason Waterman, Eleanor Birrell, Nate Foster, Fred B. Schneider, and Deborah Estrin.
  WPES 2019
  PDF
• How to Avoid Making a Billion-Dollar Mistake: Type-Safe Data Plane Programming with SafeP4
  Matthias Eichholz, Eric Campbell, Nate Foster, Guido Salvaneschi, and Mira Mezini.
  ECOOP 2019
  PDF
• TxForest: A DSL for Concurrent Data Stores
  Jonathan DiLorenzo, Kathryn Mancini, Kathleen Fisher, and Nate Foster.
  APLAS 2019
  PDF
• PicNIC: Predictable Virtualized NIC
  Praveen Kumar, Nandita Dukkipati, Nathan Lewis, Yi Cui, Yaogong Wang, Chonggang Li, Valas Valancius, Jake Adriaens, Steve Gribble, Nate Foster, and Amin Vahdat.
  SIGCOMM 2019
  🏆 Best student paper award
  PDF
• Scalable Verification of Probabilistic Networks
  Steffen Smolka, Praveen Kumar, Nate Foster, Justin Hsu, Dexter Kozen, and Alexandra Silva.
  PLDI 2019
  PDF
• Efficient, Consistent Distributed Computation with Predictive Treaties
  Tom Magrino, Jed Liu, Nate Foster, Johannes Gehrke, and Andrew C. Myers.
  EuroSys 2019
  PDF

2018

• Packet Subscriptions for Programmable ASICs
  Theo Jepsen, Masoud Moshref, Antonio Carzaniga, Nate Foster, and Robert Soule.
  HotNets 2018
  PDF
• p4v: Practical Verification for Programmable Data Planes
  Jed Liu, William Hallahan, Cole Schlesinger, Milad Sharif, Jeongkeun Lee, Robert Soule, Han Wang, Cualin Cacscaval, Nick McKeown, and Nate Foster.
  SIGCOMM 2018
  PDF
• Life in the Fast Lane: A Line-Rate Linear Road
  Theo Jepsen, Masoud Moshref, Antonio Carzaniga, Nate Foster, and Robert Soule.
  SOSR 2018
  PDF
• YATES: Rapid Prototyping for Traffic Engineering Systems
  Praveen Kumar, Chris Yu, Yang Yuan, Nate Foster, Robert Kleinberg, and Robert Soule.
  SOSR 2018
  PDF
• Semi-Oblivious Traffic Engineering: The Road Not Taken
  Praveen Kumar, Yang Yuan, Chris Yu, Nate Foster, Robert Kleinberg, Petr Lapukhov, Chiun Lin Lim, and Robert Soule.
  NSDI 2018
  PDF
• NetChain: Scale-Free Sub-RTT Coordination
  Xin Jin, Xiaozhou Li, Haoyu Zhang, Nate Foster, Jeongkeun Lee, Robert Soule, Changhoon Kim, and Ion Stoica.
  NSDI 2018
  PDF

2017

• NetCache: Balancing Key-Value Stores with Fast In-Network Caching
  Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soule, Jeongkeun Lee, Nate Foster, Changhoon Kim, and Ion Stoica.
  SOSP 2017
  PDF
• Life on the Edge: Unraveling Policies into Configurations
  Shrutarshi Basu, Nate Foster, Hossein Hojjat, Paparao Palacharla, Christian Skalka, and Xi Wang.
  ANCS 2017
  PDF
• P4FPGA: A Rapid Prototyping Framework for P4
  Han Wang, Robert Soulé, Huynh Tu Dang, Ki Suh Lee, Vishal Shrivastav, Nate Foster, and Hakim Weatherspoon.
  SOSR 2017
  PDF
• Cantor Meets Scott: Semantic Foundations for Probabilistic Networks
  Steffen Smolka, Praveen Kumar, Nate Foster, Dexter Kozen, and Alexandra Silva.
  POPL 2017
  PDF

2016

• Incremental Forest: A DSL for Efficiently Managing Filestores
  Jonathan DiLorenzo, Richard Zhang, Erin Menzies, Kathleen Fisher, and Nate Foster.
  ACM SIGPLAN Conference on Object-Oriented Programming Languages, Systems, and Applications (OOPSLA), Amsterdam, Netherlands 2016
  PDF
• Optimizing Horn Solvers for Network Repair
  Hossein Hojjat, Phillip Reummer, Jedidiah McClurg, Pavol Cerny, and Nate Foster.
  FMCAD 2016
  PDF
• Consistent Network Updates in Polynomial Time
  Pavol Cerny, Nate Foster, Nilesh Jagnik, and Jedidiah McClurg.
  DISC 2016
  PDF
• Event-Driven Network Programming
  Jedidiah McClurg, Hossein Hojjat, Nate Foster, and Pavol Cerny.
  PLDI 2016
  PDF
• Safe and Flexible Controller Upgrades for SDNs
  Karla Saur, Joseph Collard, Nate Foster, Arjun Guha, Laurent Vanbever, and Michael Hicks.
  SOSR 2016
  PDF
• Felix: Implementing Traffic Measurement on End Hosts Using Program Analysis
  Haoxian Chen, Nate Foster, Jake Silverman, Michael Whittaker, Brandon Zhang, and Rene Zhang.
  SOSR 2016
  PDF
• Probabilistic NetKAT
  Nate Foster, Dexter Kozen, Konstantinos Mamouras, Mark Reitblatt, and Alexandra Silva.
  ESOP 2016
  PDF

2015

• Formal Foundations for Networking (Dagstuhl Seminar 15071)
  Nikolaj Bjorner, Nate Foster, Philip Brighten Godfrey, and Pamela Zave.
  Dagstuhl Reports 2015
  PDF
• A Fast Compiler for NetKAT
  Steffen Smolka, Spiridon Eliopoulos, Nate Foster, and Arjun Guha.
  ICFP 2015
  PDF
• The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis
  Sudip Roy, Lucja Kot, Gabriel Bender, Bailu Ding, Hossein Hojjat, Christoph Koch, Nate Foster, and Johannes Gehrke.
  SIGMOD 2015
  PDF
• Efficient Synthesis of Network Updates
  Jedidiah McClurg, Hossein Hojjat, Pavol Cerny, and Nate Foster.
  PLDI 2015
  PDF
• A Coalgebraic Decision Procedure for NetKAT
  Nate Foster, Dexter Kozen, Mae Milano, Alexandra Silva, and Laure Thompson.
  POPL 2015
  PDF

2014

• Merlin: A Language for Provisioning Network Resources
  Robert Soul'e, Shrutarshi Basu, Parisa Jalili Marandi, Fernando Pedone, Robert Kleinberg, Emin Gun Sirer, and Nate Foster.
  CoNEXT 2014
  PDF
• Abstractions for Software-Defined Networks
  Martin Casado, Nate Foster, and Arjun Guha.
  CACM 2014
  PDF
• NetKAT: Semantic Foundations for Networks
  Carolyn Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger, and David Walker.
  POPL 2014
  PDF

2013

• Managing the Network with Merlin
  Robert Soule, Shrutarshi Basu, Robert Kleinberg, Emin Gun Sirer, and Nate Foster.
  HotNets 2013
  PDF
• Toward Synthesis of Network Updates
  Andrew Noyes, Todd Warszawski, Pavol Cerny, and Nate Foster.
  SYNT Workshop 2013
  PDF
• HotSwap: Correct and Efficient Controller Upgrades for Software-Defined Networks
  Laurent Vanbever, Joshua Reich, Theophilus Benson, Nate Foster, and Jennifer Rexford.
  HotSDN 2013
  PDF
• FatTire: Declarative Fault Tolerance for Software-Defined Networks
  Mark Reitblatt, Marco Canini, Arjun Guha, and Nate Foster.
  HotSDN 2013
  PDF
• Machine-Verified Network Controllers
  Arjun Guha, Mark Reitblatt, and Nate Foster.
  PLDI 2013
  PDF
• Composing Software Defined Networks
  Christopher Monsanto, Joshua Reich, Nate Foster, Jennifer Rexford, and David Walker.
  NSDI 2013
  🏆 Community award
  PDF
• Languages for software-defined networks
  Nate Foster, Arjun Guha, Mark Reitblatt, Alec Story, Michael J. Freedman, Naga Praveen Katta, Christopher Monsanto, Joshua Reich, Jennifer Rexford, Cole Schlesinger, David Walker, and Rob Harrison.
  IEEE Communications Magazine 2013
  PDF

2012

• Abstractions for Network Update
  Mark Reitblatt, Nate Foster, Jennifer Rexford, Cole Schlesinger, and David Walker.
  SIGCOMM 2012
  PDF
• Splendid Isolation: A Slice Abstraction for Software-Defined Networks
  Stephen Gutz, Alec Story, Cole Schlesinger, and Nate Foster.
  HotSDN 2012
  PDF
• Three Complementary Approaches to Bidirectional Programming
  Nate Foster, Kazutaka Matsuda, and Janis Voigtlander.
  Spring School on Generic and Indexed Programming (SSGIP) 2012
  PDF
• A Compiler and Run-time System for Network Programs
  Christopher Monsanto, Nate Foster, Rob Harrison, and David Walker.
  POPL 2012
  PDF
• Specifying and Verifying the Correctness of Dynamic Software Updates
  Stephen Magill, Christopher M. Hayden, Michael Hicks, Nate Foster, and Jeffrey S. Foster.
  VSTTE 2012
  PDF
• Language Abstractions for Software-Defined Networks
  Nate Foster, Michael J. Freedman, Rob Harrison, Christopher Monsanto, Mark Reitblatt, Jennifer Rexford, Alec Story, and David Walker.
  LADA Workshop 2012
  PDF
• A Pairwise Abstraction for Round-Based Protocols
  Lonnie Princehouse, Nate Foster, and Ken Birman.
  LADA Workshop 2012
  PDF

2011

• Consistent Updates for Software-Defined Networks: Change You Can Believe In!
  Mark Reitblatt, Nate Foster, Jennifer Rexford, and David Walker.
  HotNets 2011
  PDF
• Frenetic: A Network Programming Language
  Nate Foster, Rob Harrison, Michael J. Freedman, Christopher Monsanto, Jennifer Rexford, Alec Story, and David Walker.
  ICFP 2011
  PDF
• Forest: A Language and Toolkit for Programming With Filestores
  Kathleen Fisher, Nate Foster, David Walker, and Kenny Q. Zhu.
  ICFP 2011
  PDF

2010

• Frenetic: A High-Level Langauge for OpenFlow Networks
  Nate Foster, Rob Harrison, Matthew L. Meola, Michael J. Freedman, Jennifer Rexford, and David Walker.
  PRESTO Workshop 2010
  PDF
• Matching Lenses: Alignment and View Update
  Davi M. J. Barbosa, Julien Cretin, Nate Foster, Michael Greenberg, and Benjamin C. Pierce.
  ICFP 2010
  PDF

2009

• Bidirectional Programming Languages
  John Nathan Foster.
  PhD Dissertation, University of Pennsylvania 2009
  PDF
• Provenance: A Future History
  James Cheney, Stephen Chong, Nate Foster, Margo Seltzer, and Stijn Vansummeren.
  Onward! 2009
  PDF
• Bidirectional Transformations: A Cross-Discipline Perspective. GRACE Meeting notes, state of the art, and outlook
  Krzysztof Czarnecki, J. Nathan Foster, Zhenjiang Hu, Ralf Lammel, Andy Schurr, and James F. Terwilliger.
  ICMT 2009
  PDF
• Updatable Security Views
  J. Nathan Foster, Benjamin C. Pierce, and Steve Zdancewic.
  CSF 2009
  PDF

2008

• Annotated XML: Queries and Provenance
  J. Nathan Foster, Todd J. Green, and Val Tannen.
  PODS 2008
  PDF
• Boomerang: Resourceful Lenses for String Data
  Aaron Bohannon, J. Nathan Foster, Benjamin C. Pierce, Alexandre Pilkiewicz, and Alan Schmitt.
  POPL 2008
  PDF
• Quotient Lenses
  J. Nathan Foster, Alexandre Pilkiewcz, and Benjamin C. Pierce.
  ICFP 2008
  PDF
• A Generic Programming Toolkit for PADS/ML: First-Class Upgrades for Third-Party Developers
  Mary Fernandez, Kathleen Fisher, J. Nathan Foster, Michael Greenberg, and Yitzhak Mandelbaum.
  PADL 2008
  PDF
• An Algebraic Approach to XQuery View Maintenance
  J. Nathan Foster, Ravi Konuru, Jerome Simeon, and Lionel Villard.
  PLAN-X 2008
  PDF
• Boomerang Programmer's Manual
  J. Nathan Foster, and Benjamin C. Pierce.
  2008
  PDF

2007

• Provenance and Data Synchronization
  J. Nathan Foster, and Grigoris Karvounarakis.
  IEEE Data Engineering Bulletin 2007
  PDF
• A Logic Your Typechecker Can Count On: Unordered Tree Types in Practice
  J. Nathan Foster, Benjamin C. Pierce, and Alan Schmitt.
  PLAN-X 2007
  PDF
• Exploiting Schemas in Data Synchronization
  J. Nathan Foster, Michael B. Greenwald, Christian Kirkegaard, Benjamin C. Pierce, and Alan Schmitt.
  Journal of Computer and System Sciences 2007
  PDF
• Combinators for Bidirectional Tree Transformations: A Linguistic Approach to the View Update Problem
  J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt.
  TOPLAS 2007
  🏆 Most influential paper from POPL 2005
  PDF

2006

• Actions Louder Than Words? MSO-Definable Transductions
  J. Nathan Foster.
  Written Preliminary Exam II, UPenn CIS 2006
  PDF
• A Theory of Featherweight Java in Isabelle/HOL
  J. Nathan Foster, and Dimitrios Vytiniotis.
  Archive of Formal Proofs 2006
  PDF
• Harmony Programmer's Manual
  J. Nathan Foster, Benjamin C. Pierce, and Alan Schmitt.
  2006
  PDF

2005

• Harmony: A Generic Synchronization Framework for Heterogeneous, Replicated Data
  J. Nathan Foster.
  2005
  PDF
• Exploiting Schemas in Data Synchronization
  J. Nathan Foster.
  2005
  PDF
• Mechanized Metatheory for the Masses: The POPLmark Challenge
  Brian E. Aydemir, Aaron Bohannon, Matthew Fairbairn, J. Nathan Foster, Benjamin C. Pierce, Peter Sewell, Dimitrios Vytiniotis, Geoffrey Washburn, Stephanie Weirich, and Steve Zdancewic.
  TPHOLS 2005
  PDF
• Combinators for Bidirectional Tree Transformations: A Linguistic Approach to the View Update Problem
  J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt.
  POPL 2005
  PDF

2004

• LOOJ: Weaving LOOM into Java
  Kim B. Bruce, and J. Nathan Foster.
  ECOOP 2004
  PDF

2003

• Contexts, Boxes, and Names, Oh My!
  J. Nathan Foster.
  2003
  PDF
• Indexicals and Belief Reports
  J N Foster.
  MPhil Thesis, Cambridge History and Philosophy of Science and Medicine 2003
  PDF

2002

• Model Checking for a Functional Hardware Description Language
  John N Foster.
  Tripos Dissertation, Cambridge Computer Laboratory 2002
  PDF

2001

• Rupiah: Towards an Expressive Static Type System for Java
  John N Foster.
  Senior Honors Thesis, Williams Computer Science 2001
  PDF