Declarative networking with distributed recursive query processing

There have been recent proposals in the networking and distributed systems literature on declarative networking, where network protocols are declaratively specified using a recursive query language. This represents a significant new application area for recursive query processing technologies from databases. In this paper, we extend upon these recent proposals in the following ways. First, we motivate and formally define the NDlog language for declarative network specifications. We introduce the concept of link-restricted rules, which can be syntactically guaranteed to be executable via single-node derivations and message passing on an underlying network graph. Second, we introduce and prove correct relaxed versions of the traditional semi-naive execution technique that overcome fundamental problems of traditional semi-naive evaluation in an asynchronous distributed setting. Third, we consider the dynamics of network state, and formalize the “eventual consistency” of our programs even when bursts of updates can arrive in the midst of query execution. Fourth, we present a number of query optimization opportunities that arise in the declarative networking context, including applications of traditional techniques and new optimizations. Last, we present evaluation results based on an implementation of the above ideas in the P2 declarative networking system, running on 100 machines over the Emulab network testbed.