Name
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 introduce the ultimate model, which captures non-deterministic eventual outcomes of distributed programs. After showing the question of confluence undecidable for Dedalus, we identify restricted sub-languages that guarantee confluence while providing adequate expressivity. We observe that the semipositive restriction Dedalus+ guarantees confluence while capturing PTIME, but show that its restriction of negation makes certain simple and practical programs difficult to write. To remedy this, we introduce DedalusS, a restriction of Dedalus that allows a kind of stratified negation, but retains the confluence of Dedalus+ and similarly captures PTIME. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-32925-8_14 | Datalog |
Keywords | Field | DocType |
semipositive restriction dedalus,stratified negation,model-theoretic semantics,model-theoretic approach,logic programming,confluence analysis,guarantees confluence,non-deterministic eventual outcome,confluence undecidable,adequate expressivity,guarantee confluence,distributed computing,computer programming,programming languages,confluence,semantics | Programming language,Deductive database,Negation,Computer science,P,Theoretical computer science,Confluence,Logic programming,Semantics,Computer programming,Undecidable problem | Conference |
Citations | PageRank | References |
11 | 0.53 | 29 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| William R. Marczak | 1 | 274 | 12.55 |
| Peter Alvaro | 2 | 463 | 28.96 |
| Neil Conway | 3 | 458 | 21.46 |
| Joseph M. Hellerstein | 4 | 14093 | 1651.14 |
| David Maier | 5 | 5639 | 1666.90 |