Toward network data independence

ABSTRACT

A number of researchers have become interested in the design of global-scale networked systems and applications. Our thesis here is that the database community's principles and technologies have an important role to play in the design of these systems. The point of departure is at the roots of database research: we generalize Codd's notion of data independence to physical environments beyond storage systems. We note analogies between the development of database indexes and the new generation of structured peer-to-peer networks. We illustrate the emergence of data independence in networks by surveying a number of recent network facilities and applications, seen through a database lens. We present a sampling of database query processing techniques that can contribute in this arena, and discuss methods for adoption of these technologies.

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.186-201, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Artur Andrzejak , Zhichen Xu, Scalable, Efficient Range Queries for Grid Information Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.33, September 05-07, 2002
• 3: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 4: H. Balakrishnan, S. Shenker, and M. Walfish. Semantic-free referencing in linked distributed systems. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS), Feb. 2003.
• 5: Filippo Cacace , Stephano Ceri , Maurice Houtsma, A survey of parallel execution strategies for transitive closure and logic programs, Distributed and Parallel Databases, v.1 n.4, p.337-382, Oct. 1993 [doi>10.1007/BF01264013]
• 6: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 7: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 8: C. J. Date and P. Hopewell. File definition and logical data independence. In Proc. ACM SIGFIDET, pages 117--138. ACM, 1971.
• 9: Operating Systems, An Advanced Course, January 1978
• 10: David K. Gifford , Pierre Jouvelot , Mark A. Sheldon , James W. O'Toole, Jr., Semantic file systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.16-25, October 13-16, 1991, Pacific Grove, California, United States
• 11: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 12: A. Gupta, D. Agrawal, and A. E. Abbadi. Approximate range selection queries in peer-to-peer systems. In Proc. First Biennial Conference on Innovative Data Systems Research (CIDR 2003), Asilomar, CA, Jan. 2003.
• 13: J. M. Hellerstein, W. Hong, S. Madden, and K. Stanek. Beyond average: Toward sophisticated sensing with queries. In Proc. Information Processing in Sensor Networks (IPSN), 2003.
• 14: R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, and I. Stoica. Querying the internet with PIER. In Proc. 29th International Conference on Very Large Data Bases (VLDB), 2003.
• 15: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 16: J. Li, B. T. Loo, J. M. Hellerstein, M. F. Kaashoek, D. Karger, and R. Morris. On the feasibility of peer-to-peer web indexing and search. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2003.
• 17: Witold Litwin, Trie hashing, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582322]
• 18: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 19: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 20: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 21: Christos H. Papadimitriou, Database metatheory: asking the big queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212436]
• 22: V. Paxson, J. Mahdavi, A. Adams, and M. Mathis. An architecture for large-scale internet measurement. IEEE Communications, 36(8):48--54, Aug. 1998.
• 23: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 24: V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In Proc. IEEE International Conference on Data Engineering (ICDE), 2003.
• 25: S. Ratnasamay, J. M. Hellerstein, and S. Shenker. Range queries in DHTs. Technical Report IRB-TR-03-009, Intel Research, July 2003.
• 26: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 27: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 28: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 29: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 30: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
• 31: B. Yang and H. Garcia-Molina. Designing a super-peer network. In Proc. of the 19th International Conference on Data Engineering (ICDE), Mar. 2003.
• 32: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001