Dedalus: Datalog in Time and Space

Abstract

Recent research has explored using Datalog-based languages to express a distributed system as a set of logical invariants [2, 19]. Two properties of distributed systems proved difficult to model in Datalog. First, the state of any such system evolves with its execution. Second, deductions in these systems may be arbitrarily delayed, dropped, or reordered by the unreliable network links they must traverse. Previous efforts addressed the former by extending Datalog to include updates, key constraints, persistence and events, and the latter by assuming ordered and reliable delivery while ignoring delay. These details have a semantics outside Datalog, which increases the complexity of the language or its interpretation, and forces programmers to think operationally. We argue that the missing component from these previous languages is a notion of time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 16, 2009
Accession Number
ADA538767

Entities

People

  • David Maier
  • Joseph M. Hellerstein
  • Neil Conway
  • Peter Alvaro
  • Russell C. Sears
  • William R. Marczak

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Databases
  • Distributed Computing
  • Electrical Engineering
  • Engineering
  • Language
  • Semantics
  • Sequences
  • Specifications
  • Standards
  • Stratification
  • Test And Evaluation

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Computer Networking
  • Systems Analysis and Design

Technology Areas

  • Space