Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14572Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Alvaro, Peter | - |
| dc.contributor.author | AMELOOT, Tom | - |
| dc.contributor.author | Hellerstein, Joseph M. | - |
| dc.contributor.author | Marczak, William R. | - |
| dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
| dc.date.accessioned | 2013-02-06T07:59:33Z | - |
| dc.date.available | 2013-02-06T07:59:33Z | - |
| dc.date.issued | 2013 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/14572 | - |
| dc.description.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 Dedalus rules after they are modified to account for nondeterministic arrival times of messages, and augmented with control rules which model causality. The main result then is that, as far as fair operational runs are concerned, the proposed declarative semantics matches exactly the previously proposed formal operational semantics. | - |
| dc.language.iso | en | - |
| dc.subject.other | Dedalus; Datalog; distributed system; asynchronous communication; causality; operational semantics; declarative semantics; | - |
| dc.title | A Declarative Semantics for Dedalus | - |
| dc.type | Research Report | - |
| local.format.pages | 68 | - |
| local.bibliographicCitation.jcat | R2 | - |
| dc.relation.references | [1] S. Abiteboul, M. Bienvenu, A. Galland, et al. A rule-based language for Web data management. In Proceedings 30th ACM Symposium on Principles of Database Systems , pages 293–304. ACM Press, 2011. [2] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases . Addison- Wesley, 1995. [3] J.J. Alferes, L.M. Pereira, H. Przymusinska, and T.C. Przymusinski. LUPS—a language for updating logic programs. Artificial Intelligence , 138(1–2):87–116, 2002. [4] P. Alvaro, N. Conway, J. Hellerstein, and W.R. Marczak. Consistency analysis in Bloom: A CALM and collected approach. In Proceedings 5th Biennial Conference on Innovative Data Systems Research , pages 249–260. www.cidrdb.org, 2011. [5] P. Alvaro, W. Marczak, et al. Dedalus: Datalog in time and space. Tech- nical Report EECS-2009-173, University of California, Berkeley, 2009. [6] P. Alvaro, W.R. Marczak, et al. Dedalus: Datalog in time and space. In de Moor et al. [12], pages 262–281. [7] T.J. Ameloot, F. Neven, and J. Van den Bussche. Relational transducers for declarative networking. In Proceedings 30th ACM Symposium on Principles of Database Systems , pages 283–292. ACM Press, 2011. [8] T.J. Ameloot and J. Van den Bussche. Deciding eventual consistency for a simple class of relational transducers. In Proceedings of the 15th Interna- tional Conference on Database Theory , pages 86–98. ACM Press, 2012. [9] K.R. Apt and R.N. Bol. Logic programming and negation: A survey. The Journal of Logic Programming , 19-20, Supplement 1(0):9–71, 1994. [10] K.R. Apt, N. Francez, and S. Katz. Appraising fairness in languages for distributed programming. Distributed Computing , 2:226–241, 1988. [11] H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simula- tions, and Advanced Topics . Wiley, 2004. [12] O. de Moor, G. Gottlob, T. Furche, and A. Sellers, editors. Datalog Reloaded: First International Workshop, Datalog 2010 , volume 6702 of Lec- ture Notes in Computer Science , 2011. [13] A. Deutsch, L. Sui, V. Vianu, and D. Zhou. Verification of communicat- ing data-driven Web services. In Proceedings 25th ACM Symposium on Principles of Database Systems , pages 90–99. ACM Press, 2006. [14] N. Francez. Fairness . Springer-Verlag New York, Inc., New York, NY, USA, 1986. [15] M. Gelfond and V. Lifschitz. The stable model semantics for logic pro- gramming. In Proceedings of the Fifth International Conference on Logic Programming , pages 1070–1080. MIT Press, 1988. [16] G. Greco, A. Guzzo, D. Saccà, and F. Scarcello. Event choice datalog: a logic programming language for reasoning in multiple dimensions. In Proceedings of the 6th ACM SIGPLAN International Conference on Prin- ciples and Practice of Declarative Programming , PPDP, pages 238–249. ACM Press, 2004. [17] S. Grumbach and F. Wang. Netlog, a rule-based language for distributed programming. In M. Carro and R. Peña, editors, Proceedings 12th Interna- tional Symposium on Practical Aspects of Declarative Languages , volume 5937 of Lecture Notes in Computer Science , pages 88–103, 2010. [18] J.M. Hellerstein. Datalog redux: experience and conjecture. Video avail- able (under the title “The Declarative Imperative”) from http://db.cs. berkeley.edu/jmh/ , 2010. PODS 2010 keynote. [19] J.M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record , 39(1):5–19, 2010. [20] S.S. Huang, T.J. Green, and B.T. Loo. Datalog and emerging applica- tions: an interactive tutorial. In Proceedings of the 2011 ACM SIGMOD International Conference on the Management of Data , SIGMOD ’11, pages 1213–1216. ACM, 2011. [21] Trevor Jim. Sd3: A trust management system with certified evaluation. Security and Privacy, IEEE Symposium on , 0:106–115, 2001. [22] R Krishnamurthy and S.A. Naqvi. Non-deterministic choice in datalog. In Proceedings of the Third International Conference on Data and Knowledge Bases , pages 416–424, 1988. [23] L. Lamport. Fairness and hyperfairness. Distributed Computing , 13:239– 245, November 2000. [24] J. Leite and L. Soares. Adding evolving abilities to a multi-agent system. In Proceedings of the 7th International Conference on Computational Logic in Multi-agent Systems , CLIMA VII’06, pages 246–265. Springer-Verlag, 2007. [25] J.A. Leite, J.J. Alferes, and L.M. Pereira. Minerva - a dynamic logic pro- gramming agent architecture. In Revised Papers from the 8th International Workshop on Intelligent Agents VIII , ATAL, pages 141–157. Springer- Verlag, 2002. [26] B.T. Loo et al. Declarative networking. Communications of the ACM , 52(11):87–95, 2009. [27] W. Marczak, P. Alvaro, N. Conway, J.M. Hellerstein, and D. Maier. Conflu- ence analysis for distributed programs: A model-theoretic approach. Tech- nical Report UCB/EECS-2011-154, EECS Department, University of Cal- ifornia, Berkeley, Dec 2011. [28] J.A. Navarro and A. Rybalchenko. Operational semantics for declarative networking. In A. Gill and T. Swift, editors, Proceedings 11th International Symposium on Practical Aspects of Declarative Languages , volume 5419 of Lecture Notes in Computer Science , pages 76–90, 2009. [29] V. Nigam and J. Leite. A dynamic logic programming based system for agents with declarative goals. In Proceedings of the 4th International Con- ference on Declarative Agent Languages and Technologies , DALT, pages 174–190. Springer-Verlag, 2006. [30] D. Saccà and C. Zaniolo. Stable models and non-determinism in logic programs with negation. In Proceedings of the Ninth ACM Symposium on Principles of Database Systems , pages 205–217. ACM Press, 1990. [31] M. Vardi. The complexity of relational query languages. In Proceedings 14th ACM Symposium on the Theory of Computing , pages 137–146, 1982. [32] D. Zinn, T.J. Green, and B. Ludaescher. Win-move is coordination-free. In Proceedings of the 15th International Conference on Database Theory , pages 99–113. ACM Press, 2012. | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Research Report | - |
| item.accessRights | Open Access | - |
| item.fulltext | With Fulltext | - |
| item.fullcitation | Alvaro, Peter; AMELOOT, Tom; Hellerstein, Joseph M.; Marczak, William R. & VAN DEN BUSSCHE, Jan (2013) A Declarative Semantics for Dedalus. | - |
| item.contributor | Alvaro, Peter | - |
| item.contributor | AMELOOT, Tom | - |
| item.contributor | Hellerstein, Joseph M. | - |
| item.contributor | Marczak, William R. | - |
| item.contributor | VAN DEN BUSSCHE, Jan | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| dedalus.pdf | Peer-reviewed author version | 830.67 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.