the per-node communication overhead increases linearly
with the number of nodes. This suggests that our approach
does not introduce any fundamental overheads. Moreover,
when there are few nodes issuing the same query, query
optimization and work-sharing techniques can significantly
reduce the communication overhead.
One promising direction stems from our surprising
observation on the synergies between query optimization
and network routing: a wired protocol (distance-vector protocol) can be translated to a wireless protocol (dynamic source
routing) by applying the standard database optimizations of
magic sets rewrite and predicate reordering. More complex
applications of query optimization have begun to pay dividends in research, synthesizing new hybrid protocols from
traditional building blocks.
5, 17 Given the proliferation of
new routing protocols and a diversity of new network architecture proposals, the connection between query optimizations and network routing suggests that query optimizations
may help us inform new routing protocol designs and allow
the hybridization of protocols within the network.
4. 2. Declarative overlays
In declarative routing, we demonstrated the flexibility and
compactness of NDlog for specifying a variety of routing protocols. In practice, most distributed systems are much more
complex than simple routing protocols; in addition to routing, they typically also perform application-level message
forwarding and handle the formation and maintenance of
a network as well.
In our subsequent work on declarative overlays,
21 we demonstrate the use of the Overlog to implement practical application-level overlay networks. An overlay network is a virtual
network of nodes and logical links that is built on top of an
existing network with the purpose of implementing a network
service that is not available in the existing network. Examples
of overlay networks on today’s Internet include commercial
content distribution networks,
1 peer-to-peer (P2P) applications for file-sharing10 and telephony,
29 as well as a wide range
of experimental prototypes running on PlanetLab.
In declarative overlays, applications submit to P2 a concise Overlog program that describes an overlay network, and
the P2 system executes the program to maintain routing
tables, perform neighbor discovery and provide forwarding
for the overlay.
Declarative overlay programs are more complex than
routing due to the handling of message delivery, acknowledgments, failure detection, and timeouts. These programs
also heavily utilize soft-state features in Overlog not present in the original NDlog language. Despite the increased
complexity, we demonstrate that our NDlog programs are
significantly more compact compared to equivalent C++
implementations. For instance, the Narada7 mesh formation
and a full-fledged implementation of the Chord distributed
hash table30 are implemented in 16 and 48 rules, respectively. In the case of the Chord DHT presented by Loo et al.,
19
there are rules for performing various aspects of Chord,
including initial joining of the Chord network, Chord ring
maintenance, finger table maintenance, recursive Chord
lookups, and failure detection of neighbors.
We note that our Chord implementation is roughly
two orders of magnitude less code than the original C++
implementation. This is a quantitative difference that is
sufficiently large that it becomes qualitative: in our opinion
(and experience), declarative programs that are a few dozen
lines of code are markedly easier to understand, debug,
and extend than thousands of lines of imperative code.
Moreover, we demonstrate19, 21 that our declarative overlays
achieve the expected high-level properties of their respective overlay networks for both static and dynamic networks.
For example, in a static network of up to 500 nodes, the measured hop-count of lookup requests in the Chord network
conformed to the theoretical average of 0.5 × log2N hops,
and the latency numbers were within the same order of magnitude as published Chord numbers.
5. concLusion
In Jim Gray’s Turing Award Lecture,
12 one of his grand challenges was the development of “automatic programming”
techniques that would be (a) 1000× easier for people to use,
(b) directly compiled into working code, and (c) suitable for
general purpose use. Butler Lampson reiterated the first two
points in a subsequent invited article, but suggested that
they might be more tractable in domain-specific settings.
16
Declarative Networking has gone a long way toward
Gray’s vision, if only in the domain of network protocol
implementation. On multiple occasions we have seen at
least two orders of magnitude reduction in code size, with
the reduced linecount producing qualitative improvements.
In the case of Chord, a multi-thousand-line C++ library was
rewritten as a declarative program that fits on a single sheet
of paper—a software artifact that can be studied and holistically understood by a programmer in a single sitting.
We have found that a high-level declarative language not
only simplifies a programmer’s work, but refocuses the programming task on appropriately high-level issues. For example,
our work on declarative routing concluded that discussions
of routing in wired vs. wireless networks should not result in
different protocols, but rather in different compiler optimizations for the same simple declaration, with the potential to be
automatically blended into new hybrid strategies as networks
become more diverse.
5, 17 This lifting of abstractions seems
well suited to the increasing complexity of modern networking, introducing software malleability by minimizing the affor-dances for over-engineering solutions to specific settings.
Since we began our work on this topic, there has been
increasing evidence that declarative, data-centric programming has much broader applicability. Within the networking domain, we have expanded in multiple directions from
our initial work on routing, to encompass low-level network
issues at the wireless link layer6 to higher-level logic including
both overlay networks21 and applications like code dissemination, object tracking, and content distribution. Meanwhile,
a variety of groups have been using declarative programming
ideas in surprising ways in many other domains. We briefly
highlight two of our own follow-on efforts.
secure distributed systems: Despite being developed independently by separate communities, logic-based security
specifications and declarative networking programs both