Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14567
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAMELOOT, Tom-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2013-02-05T15:28:03Z-
dc.date.available2013-02-05T15:28:03Z-
dc.date.issued2012-
dc.identifier.citationBarceló, Pablo; Pichler, Reinhard (Ed.). Datalog in Academia and Industria, p. 44-55-
dc.identifier.isbn978-3-642-32924-1-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/1942/14567-
dc.description.abstractDeclarative networking is a recent approach to programming distributed applications with languages inspired by Datalog. A recent conjecture posits that the delivery of messages should respect causality if and only if they are used in non-monotone derivations. We present our results about this conjecture in the context of Dedalus, a Datalog-variant for distributed programming. We show that both directions of the conjecture fail under a strong semantical interpretation. But on a more syntactical level, we can show that positive Dedalus programs can tolerate non-causal messages, in the sense that they compute the correct answer even when messages can be sent into the past.-
dc.language.isoen-
dc.publisherSpringer-
dc.relation.ispartofseriesLecture Notes in Computer Science-
dc.subject.otherDedalus; Datalog; CRON conjecture; non-causality-
dc.titleOn the CRON Conjecture-
dc.typeProceedings Paper-
local.bibliographicCitation.authorsBarceló, Pablo-
local.bibliographicCitation.authorsPichler, Reinhard-
local.bibliographicCitation.conferencedate11-13 September 2012-
local.bibliographicCitation.conferencenameSecond International Workshop, Datalog 2.0-
local.bibliographicCitation.conferenceplaceVienna, Austria-
dc.identifier.epage55-
dc.identifier.spage44-
local.format.pages27-
local.bibliographicCitation.jcatC1-
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] P. Alvaro, T.J. Ameloot, J.M. Hellerstein, W. Marczak, and J. Van den Bussche. A declarative semantics for dedalus. Technical Report UCB/EECS-2011-120, EECS Department, University of California, Berke- ley, Nov 2011. [4] P. Alvaro, W. Marczak, et al. Dedalus: Datalog in time and space. Tech- nical Report EECS-2009-173, University of California, Berkeley, 2009. [5] P. Alvaro, W.R. Marczak, et al. Dedalus: Datalog in time and space. In 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 , pages 262–281, 2011. [6] 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. [7] T.J. Ameloot and J. Van den Bussche. Deciding eventual consistency for a simple class of relational transducer networks. In Proceedings of the 15th International Conference on Database Theory , pages 86–98. ACM Press, 2012. [8] K.R. Apt, N. Francez, and S. Katz. Appraising fairness in languages for distributed programming. Distributed Computing , 2:226–241, 1988. [9] H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simula- tions, and Advanced Topics . Wiley, 2004. [10] 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. [11] N. Francez. Fairness . Springer-Verlag New York, Inc., New York, NY, USA, 1986. [12] 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. [13] 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. [14] 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. [15] J.M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record , 39(1):5–19, 2010. [16] L. Lamport. Fairness and hyperfairness. Distributed Computing , 13:239– 245, November 2000. [17] B.T. Loo et al. Declarative networking. Communications of the ACM , 52(11):87–95, 2009. [18] 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. [19] 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. [20] 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. [21] M. Vardi. The complexity of relational query languages. In Proceedings 14th ACM Symposium on the Theory of Computing , pages 137–146, 1982. [22] Q. Zhang, L. Cheng, and R. Boutaba. Cloud computing: state-of-the-art and research challenges. Journal of Internet Services and Applications , 1:7–18, 2010. [23] 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.refereedRefereed-
local.type.specifiedProceedings Paper-
dc.identifier.doi10.1007/978-3-642-32925-8_6-
local.bibliographicCitation.btitleDatalog in Academia and Industria-
item.fulltextWith Fulltext-
item.contributorAMELOOT, Tom-
item.contributorVAN DEN BUSSCHE, Jan-
item.fullcitationAMELOOT, Tom & VAN DEN BUSSCHE, Jan (2012) On the CRON Conjecture. In: Barceló, Pablo; Pichler, Reinhard (Ed.). Datalog in Academia and Industria, p. 44-55.-
item.accessRightsOpen Access-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
cron.pdfPeer-reviewed author version578.91 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.