Communications - November 2009

failure: any data provided by failed nodes are organically “forgotten” in the absence of refreshes.

We introduced soft-state into the Overlog21 declarative networking language, an extension of NDlog. One additional feature of Overlog is the availability of a materialized keyword at the beginning of each program to specify the TTL of predicates. For example, the definition materialized(link, { 1, 2}, 10) specifies that the link table has its primary key set to the first and second fields (denoted by { 1, 2}), and each link tuple has a lifetime of 10 seconds. If the TTL is set to infinity, the predicate will be treated as hard state, i.e., a traditional relation that does not involve timeout-based deletion.

The Overlog soft-state storage semantics are as follows. When a tuple is derived, if there exists another tuple with the same primary key but differences on other fields, an update occurs, in which the new tuple replaces the previous one. On the other hand, if the two tuples are identical, a refresh occurs, in which the existing tuple is extended by its TTL.

If a given predicate has no associated materialize declaration, it is treated as an event predicate: a soft-state predicate with TTL = 0. Event predicates are transient tables, which are used as input to rules but not stored. They are primarily used to “trigger” rules periodically or in response to network events. For example, utilizing Overlog’s built-in periodic event predicate, the follo wing rule enables node X to generate a ping event every 10 seconds to its neighbor Y denoted in the link(@X, Y) predicate:

some debate about the desired semantics, focusing on attempts to provide an intuitive declarative representation while enabling familiar event-handler design patterns used by protocol developers.

3. execution PLan GeneRation

Our runtime execution of NDlog programs differs from the traditional implementation patterns for both network protocols and database queries. Network protocol implementations often center around local state machines that emit messages, triggering state transitions at other state machines. By contrast, the runtime systems we have built for NDlog and Overlog are distributed dataflow execution engines, similar in spirit to those developed for parallel database systems, and echoed in recent parallel map-reduce implementations. However, the recursion in Datalog introduces cycles into these dataflows. The combination of recursive flows and the asynchronous communication inherent in wide-area systems presents new challenges that we had to overcome.

In this section, we describe the steps required to automatically generate a distributed dataflow execution plan from an NDlog program. We first focus on generating an execution plan in a centralized implementation, before extending the techniques to the network scenario.

ping(@ Y, X) :- periodic(@X, 10), link(@X, Y).

Subtleties arise in the semantics of rules that mix event, soft-state and hard-state predicates across the head and body. One issue involves the expiry of soft-state and event tuples, as compared to deletion of hard-state tuples. In a traditional hard-state model, deletions from a rule’s body relations require revisions to the derived head relation to maintain consistency of the rule. This is treated by research on materialized view maintenance. 13 In a pure soft-state model, the head and body predicates can be left inconsistent with each other for a time, until head predicates expire due to the lack of refreshes from body predicates. Mixtures of the two models become more subtle. We provided one treatment of this issue, 19 which has subsequently been revised with a slightly different interpretation. 9 There is still

3. 1. centralized plan generation

In generating the centralized plan, we utilize the well-known semi-naïve fixpoint3 Datalog evaluation mechanism that ensures no redundant evaluations. As a quick review, in semi-naïve (SN) evaluation, input tuples computed in the previous iteration of a recursive rule execution are used as input in the current iteration to compute new tuples. Any new tuples that are generated for the first time in the current iteration, and only these new tuples, are then used as input to the next iteration. This is repeated until a fixpoint is achieved (i.e., no new tuples are produced).

The SN rewritten rule for rule sp2 is shown below:

sp2-1 Dpathnew (@Src,@Dest,Path,Cost) :-
link(@Src,Nxt,Cost1),
Dpathold(@Nxt,Dest,Path2,Cost2),
Cost=Cost1+Cost2,
Path=f_concatPath(Src,Path2).

Figure 2 shows the dataflow realization for a centralized implementation of rule sp2-1 using the conventions of P2.24

figure 2. Rule strand for a centralized implementation of rule sp2-1 in P2. output paths that are generated from the strand are “wrapped back” as input into the same strand.