Abstract
In this paper we present a language to write distributed applications. We provide an operational semantics of a single computational node based on Datalog. We then introduce a framework that can capture the semantics of a network of computational nodes working together. The framework can express several communication models (e.g. synchronous vs. asynchronous) and can be used to check many properties of the distributed computation under the different communication models. The framework is developed using Answer Set Programs.
Research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W911NF-06-3-0001. The views and conclusions are those of the authors and do not represent the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding copyright notation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Loo, B.T.: The Design and Implementation of Declarative Networks. PhD thesis, EECS Department, University of California, Berkeley (December 2006)
Loo, B.T., Condie, T., Garofalakis, M.N., Gay, D.E., Hellerstein, J.M., Maniatis, P., Ramakrishnan, R., Roscoe, T., Stoica, I.: Declarative networking: language, execution and optimization. In: SIGMOD Conference, pp. 97–108 (2006)
Li, X., Muthukumar, S.C., Liu, C., Kopena, J.B., Oprea, M., Correa, R., Loo, B.T., Basu, P.: A demonstration of the rapidmesh development toolkit. In: Proceedings of the 4th ACM International Workshop on Experimental Evaluation and Characterization, WINTECH 2009, pp. 89–90. ACM, New York (2009)
Alvaro, P., Marczak, W.R., Conway, N., Hellerstein, J.M., Maier, D., Sears, R.: Dedalus: Datalog in Time and Space. In: de Moor, O., Gottlob, G., Furche, T., Sellers, A. (eds.) Datalog 2010. LNCS, vol. 6702, pp. 262–281. Springer, Heidelberg (2011)
Gelfond, M., Lifschitz, V.: Action languages. Electron. Trans. Artif. Intell. 2, 193–210 (1998)
Greco, S., Zaniolo, C.: Greedy algorithms in datalog. Theory Pract. Log. Program. 1, 381–407 (2001)
Baral, C.: Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York (2003)
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The dlv system for knowledge representation and reasoning. ACM Trans. Comput. Logic 7, 499–562 (2006)
Simons, P., Niemelá, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138, 181–234 (2002)
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: The Potsdam answer set solving collection 24(2), 105–124 (2011)
Lamport, L.: Time clocks, and the ordering of events in a distributed system. Commun. ACM 21, 558–565 (1978)
Alvaro, P., Conway, N., Hellerstein, J., Marczak, W.R.: Consistency analysis in bloom: a calm and collected approach. In: CIDR, pp. 249–260 (2011)
Deng, Y., Grumbach, S., Monin, J.-F.: A Framework for Verifying Data-Centric Protocols. In: Bruni, R., Dingel, J. (eds.)FMOODS/FORTE 2011. LNCS, vol. 6722, pp. 106–120. Springer, Heidelberg (2011)
Ren, Y., Zhou, W., Wang, A., Jia, L., Gurney, A.J.T., Loo, B.T., Rexford, J.: Fsr: formal analysis and implementation toolkit for safe inter-domain routing. In: SIGCOMM, pp. 440–441 (2011)
Wang, A., Talcott, C., Jia, L., Loo, B.T., Scedrov, A.: Analyzing BGP Instances in Maude. In: Bruni, R., Dingel, J. (eds.) FMOODS/FORTE 2011. LNCS, vol. 6722, pp. 334–348. Springer, Heidelberg (2011)
Abiteboul, S., Abrams, Z., Haar, S., Milo, T.: Diagnosis of asynchronous discrete event systems: datalog to the rescue! In: PODS, pp. 358–367 (2005)
Abiteboul, S., Vianu, V., Fordham, B.S., Yesha, Y.: Relational transducers for electronic commerce. J. Comput. Syst. Sci. 61(2), 236–269 (2000)
Griffin, T., Wilfong, G.T.: A safe path vector protocol. In: INFOCOM, pp. 490–499 (2000)
Clausen, T., Jacquet, P.: Optimized link state routing protocol (OLSR). RFC 3236 (October 2003)
Griffin, T.G., Shepherd, F.B., Wilfong, G.: The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw. 10, 232–243 (2002)
Kakas, A.C., Kowalski, R.A., Toni, F.: Abductive logic programming. J. Log. Comput. 2(6), 719–770 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Lobo, J., Ma, J., Russo, A., Le, F. (2012). Declarative Distributed Computing. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds) Correct Reasoning. Lecture Notes in Computer Science, vol 7265. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30743-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-30743-0_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30742-3
Online ISBN: 978-3-642-30743-0
eBook Packages: Computer ScienceComputer Science (R0)