technical Perspective
narrowing the semantic Gap
in Distributed Programming
By Peter Druschel

iN sCieNCe, sigNiFiCaNT advances are often made when researchers from different communities join forces. The following paper by Hellerstein et al. is a good example. Declarative networking builds on ideas from the database, programming languages, networking, and distributed systems communities to create a novel programming paradigm for distributed systems. With declarative networking, designers express their protocols concisely using a high-level, declarative language. The program is then automatically compiled to executable code, which can be deployed in a real network.

To see why this is important, consider how distributed systems are currently implemented. Developers program the behavior of individual nodes at a low level. They use a language like C++ or Java to program a state machine that relates each possible local event (for example, message arrival, timeout) and the current state of the node to a set of local actions (for example, message transmission) and an associated change in the local state. Ultimately, designers are interested in the high-level properties of a system, such as its availability, the consistency of the results it produces, and its ability to tolerate faults. However, these properties cannot be explicitly specified nor directly observed, because they emerge from the complex interaction of the low-level, local behavior of individual nodes with each other and with the network.

When implementing a system, the programmer must specify a low-level action for each local event, while attempting to achieve the high-level, global properties. During debugging, the designer would like to assert global

properties, but can observe directly only the low-level behavior and local state of individual nodes. This semantic gap between the global, high-level properties we want to achieve and the local, low-level behavior we must specify contributes to the difficulty of implementing, debugging, and monitoring distributed systems.

Declarative networking aims to narrow this gap, thereby simplifying the task of developing correct distributed software. Developers use an extended database query language to program in a declarative fashion, which has a number of benefits.

Declarative programs are concise, can specify non-local properties directly, and abstract away many low-level details. As a result, the programs look very similar to the pseudo-code

thanks to the
authors’ efforts,
know-how from the
database, declarative
programming
and verification
communities can
be brought to bear
on the problem of
developing correct
distributed systems.

often used to describe a system’s design. Runtime queries can be added to monitor the global state of the system at the same level of abstraction as the program, which aids in the debugging and monitoring of a system. Once a distributed system is specified in this language, query optimizations and implementation techniques from the database world can be used to increase the efficiency and adaptivity of the resulting system. Lastly, declarative query languages are amenable to automated program analysis and reasoning, which can help to bring formal verification techniques to the design of practical distributed systems.

Declarative networking is a young research area and the P2 system described by the authors is not likely to be the final word on the subject. Questions remain, for instance, about the appropriate semantics of the query language, the class of distributed programs that can be expressed naturally in the declarative style, and the efficiency of distributed programs compiled from a declarative specification. However, the authors deserve much credit for breaking new ground and challenging conventional wisdom. Thanks to their efforts, know-how from the database, declarative programming and verification communities can be brought to bear on the problem of developing correct distributed systems. Moreover, developments in these areas are bound to bring further advances to declarative networking.

 

Peter Druschel ( [e-mail]) is the founding director of the Max Planck institute for Software Systems, Kaiserslautern and Saarbrücken, germany, where he leads the distributed systems research group.