Confluence Analysis for Distributed Programs: A Model-Theoretic Approach

Abstract

Building on recent interest in distributed logic programming, we take a model-theoretic approach to analyzing confluence of asynchronous distributed programs. We begin with a model-theoretic semantics for Dedalus and develop the concept of ultimate models to capture the non-deterministic eventual outcomes of distributed programs. After demonstrating the undecidability of checking confluence for Dedalus programs, we look for restricted sub-languages that guarantee confluence while providing adequate expressivity. We observe that a simple semipositive restriction called Dedalus+ guarantees confluence while capturing PTIME, but demonstrate that the limited use of negation in Dedalus+ makes certain simple and practical programs very difficult to express. To remedy this, we introduce DedalusS , a restriction of Dedalus that allows a natural use of negation in the spirit of stratified negation, but retains the confluence of Dedalus+ and similarly captures PTIME.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 18, 2011
Accession Number
ADA555874

Entities

People

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

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Confluence
  • Databases
  • Distributed Computing
  • Electrical Engineering
  • Engineering
  • Guarantees
  • Language
  • Network Protocols
  • Semantics
  • Standards
  • Words (Language)

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.
  • Systems Analysis and Design