More Web Proxy on the site http://driver.im/

article

Maintaining distributed logic programs incrementally

Authors:

Andre ScedrovAuthors Info & Claims

Computer Languages, Systems and Structures, Volume 38, Issue 2

Pages 158 - 180

https://doi.org/10.1016/j.cl.2012.02.001

Published: 01 July 2012 Publication History

Abstract

Distributed logic programming languages, which allow both facts and programs to be distributed among different nodes in a network, have been recently proposed and used to declaratively program a wide-range of distributed systems, such as network protocols and multi-agent systems. However, the distributed nature of the underlying systems poses serious challenges to developing efficient and correct algorithms for evaluating these programs. This paper proposes an efficient asynchronous algorithm to compute incrementally the changes to the states in response to insertions and deletions of base facts. Our algorithm is formally proven to be correct in the presence of message reordering in the system. To our knowledge, this is the first formal proof of correctness for such an algorithm.

References

[1]

Abiteboul, S., Hull, R. and Vianu, V., Foundations of databases. 1995. Addison-Wesley.

Digital Library

[2]

Adjiman, P., Chatalic, P., Goasdoué, F., Rousset, M.-C. and Simon, L., Distributed reasoning in a peer-to-peer setting: application to the semantic web. Journal of Artificial Intelligence Research. v25 i1. 269-314.

Digital Library

[3]

Júlio Alferes, J., Alexandre Leite, J., Moniz Pereira, L., Przymusinska, H. and Przymusinski, T.C., Dynamic logic programming. In: APPIA-GULP-PRODE, pp. 393-408.

[4]

Alvaro P, Warczak W, Conway N, Hellerstein JM, Maier D, Sears RC. Dedalus: Datalog in time and space. Technical report UCB/EECS-2009-173, EECS Department, University of California, Berkeley; December 2009.

[5]

Ashley-Rollman, M.P., Copen Goldstein, S., Lee, P., Mowry, T.C. and Pillai, P., Meld: a declarative approach to programming ensembles. In: IROS, IEEE. pp. 2794-2800.

[6]

Grumbach, S. and Wang, F., Netloga a rule-based language for distributed programming. In: PADL, pp. 88-103.

Digital Library

[7]

Gupta, A., Singh Mumick, I. and Subrahmanian, V.S., Maintaining views incrementally. In: Buneman, P., Jajodia, S. (Eds.), Proceedings of the 1993 ACM SIGMOD international conference on management of data, May 26-28, ACM Press, Washington, D.C. pp. 157-166.

Digital Library

[8]

Krishnamurthy, R., Ramakrishnan, R. and Shmueli, O., A framework for testing safety and effective computability. Journal of Computer and System Sciences. v52 i1. 100-124.

Digital Library

[9]

Liu, M., Taylor, N.E., Zhou, W., Ives, Z.G. and Thau Loo, B., Recursive computation of regions and connectivity in networks. In: ICDE, pp. 1108-1119.

Digital Library

[10]

Declarative networking: language, execution and optimization. In: SIGMOD,

Digital Library

[11]

Thau Loo, B., Hellerstein, J.M., Stoica, I. and Ramakrishnan, R., Declarative routing: extensible routing with declarative queries. In: SIGCOMM,

Digital Library

[12]

Lopes, N.P., Navarro, J.A., Rybalchenko, A. and Singh, A., Applying prolog to develop distributed systems. In: ICLP,

Digital Library

[13]

Singh Mumick, I., Pirahesh, H. and Ramakrishnan, R., The magic of duplicates and aggregates. In: VLDB '90: proceedings of the 16th international conference on very large data bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. pp. 264-277.

Digital Library

[14]

Singh Mumick, I. and Shmueli, O., Finiteness properties of database queries. In: Australian database conference, pp. 274-288.

[15]

Nigam, V., Jia, L., Thau Loo, B. and Scedrov, A., Maintaining distributed logic programs incrementally. In: PPDP, pp. 125-136.

Digital Library

[16]

Nigam, V., Jia, L., Wang, A., Loo, B.T. and Scedrov, A., An operational semantics for network datalog. In: LAM'10,

[17]

Tamer Ozsu, M. and Valduriez, P., Principles of distributed database systems. 1999. 2nd ed. Prentice Hall.

Digital Library

[18]

Paxson, V., End to end routing behavior in the internet. In: SIGCOMM '96: Conference proceedings on applications, technologies, architectures, and protocols for computer communications, ACM, New York, USA. pp. 25-38.

Digital Library

[19]

Ramakrishnan, R., Ross, K.A., Srivastava, D. and Sudarshan, S., Efficient incremental evaluation of queries with aggregation. In: SLP, pp. 204-218.

Digital Library

[20]

Ramakrishnan, R. and Ullman, J.D., A survey of research on deductive database systems. Journal of Logic Programming. v23 i2. 125-149.

[21]

Wang, A., Basu, P., Loo, B.T. and Sokolsky, O., Declarative network verification. In: Eleventh international symposium on practical aspects of declarative languages (PADL),

Digital Library

[22]

Wang, A., Jia, L., Liu, C., Loo, B.T., Sokolsky, O. and Basu, P., Formally verifiable networking. In: ACM SIGCOMM HotNets-VIII,

Cited By

Di Cosmo F(2023)Decidability Borders of Verification of Communicating Datalog AgentsMulti-Agent Systems10.1007/978-3-031-43264-4_39(507-513)Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43264-4_39
Qayyum OYu WHong JBures MPark JCerny T(2022)Toward replicated and asynchronous data streams for edge-cloud applicationsProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507687(339-346)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507687
Nigam VReis GRahmouni SRuess H(2021)Proof Search and Certificates for Evidential TransactionsAutomated Deduction – CADE 2810.1007/978-3-030-79876-5_14(234-251)Online publication date: 12-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-79876-5_14
Show More Cited By

Recommendations

Maintaining distributed logic programs incrementally
PPDP '11: Proceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming

Distributed logic programming languages, that allow both facts and programs to be distributed among different nodes in a network, have been recently proposed and used to declaratively program a wide-range of distributed systems, such as network ...
A refinement calculus for logic programs

Existing refinement calculi provide frameworks for the stepwise development of imperative programs from specifications. This paper presents a refinement calculus for deriving logic programs. The calculus contains a wide-spectrum logic programming ...
Correctness and Completeness of Logic Programs

We discuss proving correctness and completeness of definite clause logic programs. We propose a method for proving completeness, while for proving correctness we employ a method that should be well known but is often neglected. Also, we show how to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Languages, Systems and Structures

Computer Languages, Systems and Structures Volume 38, Issue 2

July, 2012

76 pages

ISSN:1477-8424

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2012.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Di Cosmo F(2023)Decidability Borders of Verification of Communicating Datalog AgentsMulti-Agent Systems10.1007/978-3-031-43264-4_39(507-513)Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43264-4_39
Qayyum OYu WHong JBures MPark JCerny T(2022)Toward replicated and asynchronous data streams for edge-cloud applicationsProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507687(339-346)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507687
Nigam VReis GRahmouni SRuess H(2021)Proof Search and Certificates for Evidential TransactionsAutomated Deduction – CADE 2810.1007/978-3-030-79876-5_14(234-251)Online publication date: 12-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-79876-5_14
Di Cosmo F(2019)The Impact of Propositional Messages on Termination of Declarative Distributed SystemsSelected Reflections in Language, Logic, and Information10.1007/978-3-031-50628-4_4(44-79)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-031-50628-4_4
Interlandi MTetali SGulzar MNoor JCondie TKim MMillstein T(2016)Optimizing Interactive Development of Data-Intensive ApplicationsProceedings of the Seventh ACM Symposium on Cloud Computing10.1145/2987550.2987565(510-522)Online publication date: 5-Oct-2016
https://dl.acm.org/doi/10.1145/2987550.2987565
Ameloot T(2015)Deciding Determinism with Fairness for Simple Transducer NetworksACM Transactions on Database Systems10.1145/275721540:2(1-39)Online publication date: 30-Jun-2015
https://dl.acm.org/doi/10.1145/2757215
Ameloot T(2014)Declarative NetworkingACM SIGMOD Record10.1145/2694413.269441543:2(5-16)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1145/2694413.2694415
Ameloot TNeven FVan Den Bussche J(2013)Relational transducers for declarative networkingJournal of the ACM10.1145/2450142.245015160:2(1-38)Online publication date: 3-May-2013
https://dl.acm.org/doi/10.1145/2450142.2450151

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents