Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Declarative Semantics for Dedalus

Peter Alvaro, Tom J. Ameloot, Joseph M. Hellerstein, William Marczak and Jan Van den Bussche

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2011-120
November 29, 2011

http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-120.pdf

The language Dedalus is a Datalog-like language in which distributed computations and networking protocols can be programmed, in the spirit of the Declarative Networking paradigm. Whereas recently formal, operational, semantics for Dedalus-like languages have been developed, a purely declarative semantics has been lacking so far. The challenge is to capture precisely the amount of nondeterminism that is inherent to distributed computations due to concurrency, networking delays, and asynchronous communication. This paper shows how a declarative semantics can be obtained by simply using the well-known stable model semantics for Datalog with negation. This semantics is applied to the orig- inal Dedalus rules, modified to account for nondeterministic choices, and augmented with control rules which model causality. The main result then is that, as far as fair runs are concerned, the proposed declarative semantics matches exactly the previously proposed formal operational semantics.


BibTeX citation:

@techreport{Alvaro:EECS-2011-120,
    Author = {Alvaro, Peter and Ameloot, Tom J. and Hellerstein, Joseph M. and Marczak, William and Van den Bussche, Jan},
    Title = {A Declarative Semantics for Dedalus},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2011},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-120.html},
    Number = {UCB/EECS-2011-120},
    Abstract = {The language Dedalus is a Datalog-like language in which distributed computations and networking protocols can be programmed, in the spirit of the Declarative Networking paradigm. Whereas recently formal, operational, semantics for Dedalus-like languages have been developed, a purely declarative semantics has been lacking so far. The challenge is to capture precisely the amount of nondeterminism that is inherent to distributed computations due to concurrency, networking delays, and asynchronous communication. This paper shows how a declarative semantics can be obtained by simply using the well-known stable model semantics for Datalog with negation. This semantics is applied to the orig- inal Dedalus rules, modified to account for nondeterministic choices, and augmented with control rules which model causality. The main result then is that, as far as fair runs are concerned, the proposed declarative semantics matches exactly the previously proposed formal operational semantics.}
}

EndNote citation:

%0 Report
%A Alvaro, Peter
%A Ameloot, Tom J.
%A Hellerstein, Joseph M.
%A Marczak, William
%A Van den Bussche, Jan
%T A Declarative Semantics for Dedalus
%I EECS Department, University of California, Berkeley
%D 2011
%8 November 29
%@ UCB/EECS-2011-120
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-120.html
%F Alvaro:EECS-2011-120