Home

Declarative Networking: Language, Execution and Optimization

Declarative Networking: Language, Execution and Optimization, Boon Thau Loo, Tyson Condie, Minos Garofalakis, David A. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe and Ion Stoica.

First, we motivate and formally define the Network Datalog (NDlog) language for declarative network specifications.
Second, we introduce and prove correct relaxed versions of the traditional semi-naive query evaluation technique, to overcome fundamental problems of the traditional technique 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 as well as new optimizations. Last, we present evaluation results of the above ideas implemented in our P2 declarative networking system, running on 100 machines over the Emulab network testbed.

I will be the first to admit that I somehow fundamentally do not get the logic programming style, but presenting a routing discovery protocol in about eight lines of code is pretty cool.

By Tommy McGuire at 2006-08-23 22:46 | DSL | Logic/Declarative | other blogs | 8381 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Large datasets and Implementations?

This programming model looks very nice. I would like to apply it to a different problem, keeping front-end serving systems equipped with up-to-date summaries of large back-end databases. This paper seems to only address small problems like shortest-path, but I don't see any reason the ideas shouldn't scale. I've been looking for efficient implementations of similar models, but I have no background so I haven't been finding anything.

By Brandon Moore at Mon, 2006-08-28 19:36 | login or register to post comments

Distribution Control

Playing with this model a little, it seems to provide a lot of control over communication and data distribution with little effort.

For example, it's easy to express partitioning and replicated storage of tables. Rather than
relation(@target, Cols) :- #link(@target, @Src), rules(@Src, Cols)
(where @target is a location literal) write something like
relation(@Target, Cols) :- #link(@Target, @Src), replica(@Target, Partition), partition(Partition, Cols), rules(@Src, Cols)
where the relation partition computes which partition of the result should hold a tuple, and replica associates a partition id with all locations that hold replicas of that partition.

I don't see how to express sending a row to one of an arbitrary choice of locations, but it seems that would confound deletes or updates chasing the row.

By Brandon Moore at Mon, 2006-08-28 19:44 | login or register to post comments