SEND to linkD.Nxt
SEND to path. Src
SEND to path.Src
Src sends all existing links to the destination address field
as linkD tuples. Rule strand sp2b- 2@Nxt takes the new
linkD tuples it received via the network and performs a join
operation with the local path table to generate new paths.
3. 3. Relaxing semi-naïve evaluation
In our distributed implementation, the execution of rule
strands can depend on tuples arriving via the network, and
can also result in new tuples being sent over the network.
Traditional SN evaluation completely evaluates all rules on
a given set of facts, i.e., completes the iteration, before considering any new facts. In a distributed execution environment where messages can be delayed or lost, the completion
of an iteration in the traditional sense can only be detected
by a consensus computation across multiple nodes, which
is expensive; further, the requirement that many nodes complete the iteration together (a “barrier synchronization” in parallel computing terminology) limits parallelism significantly
by restricting the rate of progress to that of the slowest node.
We address this by making the notion of iteration local
to a node. New facts might be generated through local rule
execution, or might be received from another node while a
local iteration is in progress. We proposed and proved correct a variation of SN iteration called pipelined semi-naïve
(PSN) to handle this situation.
20 PSN extends SN to work in
an asynchronous distributed setting. PSN relaxes SN evaluation to the extreme of processing each tuple as it is received.
This provides opportunities for additional optimizations on
a per-tuple basis. New tuples that are generated from the SN
rules, as well as tuples received from other nodes, are used
immediately to compute new tuples without waiting for the
current (local) iteration to complete.
algorithm 2 Pipelined Semi-naïve (PSN) Evaluation
Qk.size > 0
foreach rule strand execution
Dpj new, i+
1 : —
1, tkold,i, pk+
1,..., pn, b1, b2,..., bm
foreach tjnew, i+
1 Î Dpj new, i+
1 Ï pj
then pj ¬ pj È tjnew,i+
Qj.enqueue Tuple (tjnew,i+
Algorithm 2 shows the pseudocode for PSN. Each tuple,
denoted t, has a superscript (old/new, i) where i is its corresponding iteration number in SN evaluation. Each processing step in PSN consists of dequeuing a tuple tkold,i from Qk
and then using it as input into all corresponding rule strands.
Each resulting tjnew, i+
1 tuple is pipelined, stored in its respective
pj table (if a copy is not already there), and enqueued into Qj for
further processing. Note that in a distributed implementation.
Qj can be a queue on another node, and the node that receives
the new tuple can immediately process the tuple after the
enqueue into Qj. For example, the dataflow in Figure 4 is based
on a distributed implementation of PSN, where incoming
path and linkD tuples received via the network are stored
locally, and enqueued for processing in the corresponding
To fully pipeline evaluation, we have also removed the distinctions between pjold and pj in the rules. Instead, a timestamp
(or monotonically increasing sequence number) is added to
each tuple at arrival, and the join operator matches each tuple
only with tuples that have the same or older timestamp. This
allows processing of tuples immediately upon arrival, and is
natural for network message handling. This represents an
alternative “book-keeping” strategy to the rewriting used in SN
to ensure no repeated inferences. Note that the timestamp only
needs to be assigned locally, since all the rules are localized.
We have proven elsewhere20 that PSN generates the same
results as SN and does not repeat any inferences, as long as
the NDlog program is monotonic and messages between two
network nodes are delivered in FIFO order.
3. 4. incremental maintenance
In practice, most network protocols are executed over a long
period of time, and the protocol incrementally updates and
repairs routing tables as the underlying network changes
(link failures, node departures, etc.). To better map into
practical networking scenarios, one key distinction that
differentiates the execution of NDlog from earlier work in
Datalog is our support for continuous rule execution and
result materialization, where all tuples derived from NDlog
rules are materialized and incrementally updated as the
underlying network changes. As in network protocols,
such incremental maintenance is required both for timely
updates and for avoiding the overhead of recomputing all
routing tables “from scratch” whenever there are changes