extend Datalog in surprisingly similar ways: by supporting the notion of context (location) to identify components (nodes) in distributed systems. The Secure Network Datalog33 language extends NDlog with basic security constructs for implementing secure distributed systems, which are further enhanced with type checking and meta-programmability in the LBTrust23 system for supporting various forms of encryption/authenti-cation, delegation, for distributed trust management. datacenter Programming: The BOOM2 project is exploring the use of declarative languages in the setting of Cloud Computing. Current cloud platforms provide developers with sequential programming models that are a poor match for inherently distributed resources. To illustrate the benefits of declarative programming in a cloud, we used Overlog as the basis for a radically simplified and enhanced reimple-mentation of a standard cloud-based analytics stack: the Hadoop File System (HDFS) and MapReduce infrastructure. Our resulting system is API-compatible with Hadoop, with performance that is equivalent or better. More significantly, the high-level Overlog specification of key Hadoop internals enabled a small group of graduate students to quickly add sophisticated distributed features to the system that are not in Hadoop: hot standby master nodes supported by MultiPaxos consensus, scaleout of (quorums of) master nodes via data partitioning, and implementations of new scheduling protocols and query processing strategies.

In addition to these two bodies of work, others have successfully adopted concepts from declarative networking, in the areas of mobility-based overlays, adaptively hybridized mobile ad-hoc networks, overlay network composition, sensor networking, fault-tolerant protocols, network configuration, replicated filesystems, distributed machine learning algorithms, and robotics. Outside the realm of networking and distributed systems, there has been an increasing use of declarative languages—many rooted in Datalog—to a wide range of problems including natural language processing, compiler analysis, security, and computer games. We maintain a list of related declarative languages and research projects at http://declarativity.net/related.

For the moment, these various efforts represent individual instances of Lampson’s domain-specific approach to Gray’s automatic programming challenge. In the coming years, it will be interesting to assess whether these solutions prove fruitful, and whether it is feasible to go after Gray’s challenge directly: to deliver an attractive general-purpose declarative programming environment that radically simplifies wide range of tasks.

 

1. akamai. akamai Content Distribution network. 2006. http://www.akamai.com.

2. alvaro, P., Condie, t., Conway, n., elmeleegy, K., hellerstein, J.M., Sears, r.C. booM: Data-centric programming in the datacenter. technical report UCb/eeCS-2009- 98, eeCS Department, University of California, berkeley, Jul 2009.

3. balbin i., ramamohanarao, K. a generalization of the differential approach to recursive query evaluation. J. Logic Prog. 4, 3 (1987), 259–262.

4. bancilhon, f., Maier, D., Sagiv, y., Ullman, J. Magic sets and other strange ways to implement logic

References

programs. in Proceedings of ACM SIGMOD International Conference on Management of Data (1986).

5. Chu, D., hellerstein, J. automating rendezvous and proxy selection in sensor net works. in Eighth International Conference on Information Processing in Sensor Networks (IPSN) (2009).

6. Chu, D.C., Popa, L., tavakoli, a., hellerstein, J.M., Levis, P., Shenker, S., Stoica, i. the design and implementation of a declarative sensor network system. in 5th ACM Conference on Embedded Networked Sensor Systems (SenSys) (2007).

7. Chu, y.-h., rao, S.g., Zhang, h. a case for end system multicast. in Proceedings of ACM SIGME TRICS (2000), 1–12.

8. Clark, D.D. the design philosophy of the DarPa internet protocols. in Proceedings of ACM SIGCOMM Conference on Data Communication (Stanford, Ca, 1988), aCM, 106–114.

9. Condie, t., Chu, D., hellerstein, J. M., Maniatis, P. evita raced: metacompilation for declarative networks. in Proceedings of VLDB Conference (2008).

10. gnutella. http://www.gnutella.com.

11. graefe, g. encapsulation of parallelism in the volcano query processing system. in Proceedings of ACM SIGMOD International Conference on Management of Data (1990).

12. gray, J. What next? a few remaining problems in information technlogy, SigMoD Conference 1999. aCM turing award Lecture, Video. ACM SIGMOD Digital Symposium Collection 2, 2 (2000).

13. gupta, a., Mumick, i.S., Subrahmanian, V.S. Maintaining views incrementally. in Proceedings of ACM SIGMOD International Conference on Management of Data (1993).

14. Kohler, e., Morris, r., Chen, b., Jannotti, J., Kaashoek, M.f. the click modular router. ACM Trans. Comp. Sys. 18, 3 (2000), 263–297.

15. Krishnamurthy, r., ramakrishnan, r., Shmueli, o. a framework for testing safety and effective computability. J. Comp. Sys. Sci. 52, 1 (1996), 100–124.

16. Lampson, b. getting computers to understand. J. ACM 50, 1 (2003), 70–72.

17. Liu, C., Correa, r., Li, x., basu, P., Loo, b.t., Mao, y. Declarative Policy-based adaptive Manet routing. in 17th IEEE International Conference on Network Protocols (ICNP) (2009).

18. Liu, M., taylor, n., Zhou, W., ives, Z., Loo, b.t. recursive computation of regions and connectivity in networks. in Proceedings of IEEE Conference on Data Engineering (ICDE) (2009).

19. Loo, b.t. the Design and implementation of Declarative networks (Ph.D. Dissertation). technical report UCb/eeCS-2006- 177, UC berkeley (2006).

20. Loo, b.t., Condie, t., garofalakis, M., gay, D.e., hellerstein, J.M., Maniatis, P., ramakrishnan, r., roscoe, t.,

 

Boon Thau Loo ( [e-mail]) University of Pennsylvania, Philadelphia, Pa. Tyson Condie ( [e-mail]) University of California, berkeley, Ca.

Minos Garofalakis ( [e-mail]) technical University of Crete, greece. David E. Gay ( [e-mail]) intel research, berkeley, Ca.

Stoica, i. Declarative networking: language, execution and optimization. in Proceedings of ACM SIGMOD International Conference on Management of Data (2006).

21. Loo, b.t., Condie, t., hellerstein, J.M., Maniatis, P., roscoe, t., Stoica, i. implementing declarative overlays. in Proceedings of ACM Symposium on Operating Systems Principles (2005).

22. Loo, b.t., hellerstein, J.M., Stoica, i., ramakrishnan, r. Declarative routing: extensible routing with declarative queries. in Proceedings of ACM SIGCOMM Conference on Data Communication (2005).

23. Marczak, W.r., Zook, D., Zhou, W., aref, M., Loo, b.t. Declarative reconfigurable trust management. in Proceedings of Conference on Innovative Data Systems Research (CIDR) (2009).

24. P2: Declarative networking System. http://p2.cs.berkeley.edu.

25. Perez, J.n., rybalchenko, a., Singh, a. Cardinality abstraction for declarative networking applications. in Proceedings of Computer Aided Verification (CAV) (2009).

26. PlanetLab. global testbed. 2006. http://www.planet-lab.org/.

27. ramakrishnan, r., Ullman, J.D. a survey of research on deductive database systems. J. Logic Prog. 23, 2 (1993), 125–149.

28. Singh, a., Maniatis, P., roscoe, t., Druschel, P. Distributed monitoring and forensics in overlay networks. in Proceedings of Eurosys (2006).

29. Skype. Skype P2P telephony. 2006. http://www.skype.com.

30. Stoica, i., Morris, r., Karger, D., Kaashoek, M.f., balakrishnan, h. Chord: a scalable P2P lookup service for internet applications. in SIGCOMM (2001).

31. tennenhouse, D. L., Smith, J.M., Sincoskie, W.D., Wetherall, D.J., Minden, g. J. a survey of active network research. IEEE Commun. Mag. 35, 1 (1997), 80–86.

32. Wang, a., basu, P., Loo, b.t., Sokolsky, o. towards declarative network verification. in 11th International Symposium on Practical Aspects of Declarative Languages (PADL) (2009).

33. Zhou, W., Mao, y., Loo, b.t., abadi, M. Unified declarative platform for secure networked information systems. in Proceedings of IEEE Conference on Data Engineering (ICDE) (2009).

 

Joseph M. hellerstein (hellerstein@ cs.berkeley.edu) University of California, berkeley, Ca. Petros Maniatis ( petros.maniatis@intel. com) intel research, berkeley, Ca.

Raghu Ramakrishnan (ramakris@yahoo- inc.com) yahoo! research, Silicon Valley. Timothy Roscoe ( [e-mail]) eth Zurich, Switzerland.

Ion Stoica ( [e-mail]) University of California, berkeley, Ca.