Our main contributions are as follows. First, we formally define the Network Datalog (NDlog) language based on extensions to the Datalog recursive query language, and propose NDlog as a Domain Specific Language for programming network protocols. We demonstrate that NDlog can be used to express a large variety of network protocols in a handful of lines of program code, resulting in orders of magnitude reduction in code size. For example, the Chord overlay network can be specified in 48 NDlog rules. In addition, the core of the language (Datalog) has polynomial complexity, and our NDlog extensions can be statically analyzed for termination using standard analysis techniques.

Second, to validate the design of NDlog, we present our implementation of P2, which is a full-fledged declarative networking system that compiles NDlog and executes it via a dataflow engine inspired by the Click modular router. We experimentally evaluate the P2 system on hundreds of distributed machines. The P2 system is publicly available for download and has been used in research projects at a number of institutions.

Third, based on our experiences implementing declarative networks, we explore a wide variety of database research issues that are important for the practical realization of declarative networks. These include pipelined execution of distributed recursive queries, reasoning about query semantics based on the well-known distributed systems notion of "eventual consistency", incorporating the notion of soft-state into the logical framework of NDlog, and the use of query optimizations to improve the performance of network protocols.