Hostname: page-component-8448b6f56d-42gr6 Total loading time: 0 Render date: 2024-04-16T19:29:23.227Z Has data issue: false hasContentIssue false
  • English
  • Français

Applying Prolog to develop distributed systems

Published online by Cambridge University Press:  09 July 2010

NUNO P. LOPES ,
JUAN A. NAVARRO ,
ANDREY RYBALCHENKO  and
ATUL SINGH
NUNO P. LOPES
Affiliation:
INESC-ID, Instituto Superior Técnico – Technical University of Lisbon, Portugal
JUAN A. NAVARRO
Affiliation:
Technische Universität München, Munich, Germany
ANDREY RYBALCHENKO
Affiliation:
Technische Universität München, Munich, Germany
ATUL SINGH
Affiliation:
NEC Research Labs, Princeton, NJ, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

Development of distributed systems is a difficult task. Declarative programming techniques hold a promising potential for effectively supporting programmer in this challenge. While Datalog-based languages have been actively explored for programming distributed systems, Prolog received relatively little attention in this application area so far. In this paper we present a Prolog-based programming system, called DAHL, for the declarative development of distributed systems. DAHL extends Prolog with an event-driven control mechanism and built-in networking procedures. Our experimental evaluation using a distributed hash-table data structure, a protocol for achieving Byzantine fault tolerance, and a distributed software model checker—all implemented in DAHL—indicates the viability of the approach.

Keywords

distributed systemslogic programmingProlog
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 10 , Special Issue 4-6: 26th International Conference on Logic Programming , July 2010 , pp. 691 - 707
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alvaro, P., Condie, T., Conway, N., Elmeleegy, K., Hellerstein, J. M. and Sears, R. C. 2009. BOOM: Data-Centric Programming in the Datacenter. Technical Report UCB/EECS-2009-98, EECS Department, University of California, Berkeley.Google Scholar
Alvaro, P., Condie, T., Conway, N., Hellerstein, J. M. and Sears, R. 2010. I Do Declare: Consensus in a Logic Language. ACM SIGOPS Operating Systems Review 43, 4, 25–30.Google Scholar
Armstrong, J., Virding, R., Wikström, C. and Williams, M. 1993. Concurrent Programming in ERLANG. Prentice Hall.Google Scholar
Ashley-Rollman, M., Goldstein, S., Lee, P., Mowry, T. and Pillai, P. 2007. Meld: A declarative approach to programming ensembles. In IEEE/RSJ International Conference on Intelligent Robots and Systems. 2794–2800.CrossRefGoogle Scholar
Ashley-Rollman, M. P., Lee, P., Goldstein, S. C., Pillai, P. and Campbell, J. D. 2009. A language for large ensembles of independently executing nodes. In ICLP '09: Proceedings of the 25th International Conference on Logic Programming. Springer, Berlin, 265–280.Google Scholar
Bal, H. E. 1993. Evaluation of KL1 and the inference machine. Future Generation Computer Systems 9, 2, 119–125.Google Scholar
Banerjee, S., Bhattacharjee, B. and Kommareddy, C. 2002. Scalable Application Layer Multicast. In SIGCOMM '02: Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. ACM, New York, 205–217.CrossRefGoogle Scholar
Belaramani, N., Zheng, J., Nayate, A., Soulé, R., Dahlin, M. and Grimm, R. 2008. PADRE: A policy architecture for building data REplication systems. Technical Report TR-08-25, University of Texas, Austin.Google Scholar
Biagioni, E., Harper, R. and Lee, P. 2001. A network protocol stack in standard ML. Higher Order Symbolic Computation 14, 4, 309–356.Google Scholar
Casas, A., Carro, M. and Hermenegildo, M. V. 2008. A high-level implementation of non-deterministic, unrestricted, independent and-parallelism. In ICLP '08: Proceedings of the 24th International Conference on Logic Programming. Springer, Berlin, 651–666.Google Scholar
Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A. and Singh, A. 2003. SplitStream: High-bandwidth multicast in cooperative environments. In SOSP '03: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles. ACM, New York, 298–313.CrossRefGoogle Scholar
Chu, D., Popa, L., Tavakoli, A., Hellerstein, J. M., Levis, P., Shenker, S. and Stoica, I. 2007. The design and implementation of a declarative sensor network system. In SenSys '07: Proceedings of the 5th International Conference on Embedded Networked Sensor Systems. ACM, New York, 175–188.CrossRefGoogle Scholar
Chu, Y.-h., Ganjam, A., Ng, T. S. E., Rao, S. G., Sripanidkulchai, K., Zhan, J. and Zhang, H. 2004. Early experience with an internet broadcast system based on overlay multicast. In ATEC '04: Proceedings of the Annual Conference on USENIX Annual Technical Conference. USENIX Association, Berkeley, CA, 12–12.Google Scholar
Clement, A., Wong, E., Alvisi, L., Dahlin, M., and Marchetti, M. 2009. Making Byzantine fault tolerant systems tolerate byzantine faults. In NSDI'09: Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, Berkeley, CA, 153–168.Google Scholar
Grumbach, S. and Wang, F. 2010. Netlog, a rule-based language for distributed programming. In PADL'10: Proceedings of the Eleventh International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 5937. Springer, 88–103.CrossRefGoogle Scholar
Gupta, G., Pontelli, E., Ali, K. A., Carlsson, M. and Hermenegildo, M. V. 2001. Parallel execution of prolog programs: A survey. ACM Transactions on Programming Languages and Systems 23, 4, 472–602.CrossRefGoogle Scholar
Jannotti, J., Gifford, D. K., Johnson, K. L., Kaashoek, M. F. and O'Toole, J. W. Jr. 2000. Overcast: Reliable Multicasting with an Overlay Network. In OSDI'00: Proceedings of the 4th conference on Symposium on Operating System Design and Implementation. USENIX Association, Berkeley, CA, 14–14.Google Scholar
Killian, C. E., Anderson, J. W., Braud, R., Jhala, R., and Vahdat, A. M. 2007. Mace: Language support for building distributed systems. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 179–188.Google Scholar
Killian, C. E., Anderson, J. W., Jhala, R. and Vahdat, A. 2007. Life, death, and the critical transition: Finding liveness bugs in systems code. In NSDI'07: Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, Berkeley, CA.Google Scholar
Kotla, R., Alvisi, L., Dahlin, M., Clement, A. and Wong, E. 2007. Zyzzyva: Speculative Byzantine fault tolerance. ACM SIGOPS Operating Systems Review 41, 6, 45–58.CrossRefGoogle Scholar
Leonini, L., Rivière, E. and Felber, P. 2009. SPLAY: Distributed systems evaluation made simple. In NSDI'09: Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, Berkeley, CA, 185–198.Google Scholar
Li, B., Xie, S., Keung, G., Liu, J., Stoica, I., Zhang, H. and Zhang, X. 2007. An empirical study of the Coolstreaming+ System. IEEE Journal on Selected Areas in Communications 25, 9 (Dec.), 1627–1639.Google Scholar
Loo, B. T., Condie, T., Garofalakis, M., Gay, D. E., Hellerstein, J. M., Maniatis, P., Ramakrishnan, R., Roscoe, T. and Stoica, I. 2006. Declarative networking: Language, execution and optimization. In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. ACM, New York, 97–108.CrossRefGoogle Scholar
Loo, B. T., Condie, T., Hellerstein, J. M., Maniatis, P., Roscoe, T. and Stoica, I. 2005. Implementing declarative overlays. ACM SIGOPS Operating Systems Review 39, 5, 75–90.CrossRefGoogle Scholar
Lopes, N. P. and Rybalchenko, A. 2010. Distributed and predictable software model checking. Draft manuscript.Google Scholar
Madhavapeddy, A., Ho, A., Deegan, T., Scott, D. and Sohan, R. 2007. Melange: Creating a “Functional” Internet. In EuroSys '07: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems. ACM, New York, 101–114.Google Scholar
Mao, Y. 2010. On the declarativity of declarative networking. ACM SIGOPS Operating Systems Review 43, 4, 19–24.Google Scholar
Mathewson, N. and Provos, N. 2009. libevent Documentation. Release 1.4.9.Google Scholar
Navarro, J. A. and Rybalchenko, A. 2009. Operational Semantics for Declarative Networking. In PADL '09: Proceedings of the 11th International Symposium on Practical Aspects of Declarative Languages. Springer, Berlin, 76–90.Google Scholar
Pérez, J. A., Rybalchenko, A. and Singh, A. 2009. Cardinality abstraction for declarative networking applications. In CAV '09: Proceedings of the 21st International Conference on Computer Aided Verification. Springer, Berlin, 584–598.CrossRefGoogle Scholar
Rhea, S., Geels, D., Roscoe, T. and Kubiatowicz, J. 2004. Handling churn in a DHT. In ATEC '04: Proceedings of the Annual Conference on USENIX Annual Technical Conference. USENIX Association, Berkeley, CA, 10–10.Google Scholar
Singh, A., Das, T., Maniatis, P., Druschel, P., and Roscoe, T. 2008. BFT protocols under fire. In NSDI'08: Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, Berkeley, CA, 189–204.Google Scholar
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. 2001. Chord: A scalable peer-to-peer lookup service for Internet applications. ACM SIGCOMM Computer Communication Review 31, 4, 149–160.Google Scholar
The Intelligent Systems Laboratory. 2009. SICStus Prolog User's Manual. Swedish Institute of Computer Science. Release 4.0.5.Google Scholar
Vahdat, A., Yocum, K., Walsh, K., Mahadevan, P., Kostić, D., Chase, J. and Becker, D. 2002. Scalability and accuracy in a large-scale network emulator. ACM SIGOPS Operating Systems Review 36, SI, 271–284.CrossRefGoogle Scholar
Wang, A., Basu, P., Loo, B. T. and Sokolsky, O. 2009. Declarative network verification. In PADL '09: Proceedings of the 11th International Symposium on Practical Aspects of Declarative Languages. Springer, Berlin, 61–75.Google Scholar
White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M., Barb, C. and Joglekar, A. 2002. An integrated experimental environment for distributed systems and networks. ACM SIGOPS Operating Systems Review 36, SI, 255–270.CrossRefGoogle Scholar
Yabandeh, M., Knežević, N., Kostić, D. and Kuncak, V. 2010. Predicting and preventing inconsistencies in deployed distributed systems. ACM Transactions on Computer Systems 28, 1, 1–49.CrossRefGoogle Scholar