The networking and distributed systems communities have recently explored a variety of new network architectures, both for application- level overlay networks, and as prototypes for a next-generation In ternet architecture. In this context, we have investigated declarative networking: the use of a distributed recursive query engine as a powerful vehicle for accelerating innovation in network architectures [23, 24, 33]. Declarative networking represents a significant new application area for database research on recursive query processing. In this paper, we address fundamental database issues in this domain.