P2P systems with transactional semantics

ABSTRACT

Structured P2P systems have been developed for constructing applications at internet scale in cooperative environments and exhibit a number of desirable features such as scalability and self-maintenance. We argue that such systems when augmented with well defined consistency semantics provide an attractive building block for many large scale data processing applications in cluster environments. Towards this end, we study the problem of providing transactional semantics to P-Ring a P2P system which supports efficient range queries. We first extend a commonly used replication protocol in P2P systems to provide well defined guarantees in the presence of concurrent updates and under well defined failure assumptions. A multi-version concurrency control protocol called LSTP which leverages the guarantees of the replication protocol to provide transactional semantics is proposed. LSTP is designed to provide useful consistency semantics over P-Ring for read intensive workloads without sacrificing the scalability and other desirable properties inherent to the system. Under LSTP, read-only transactions are abort-free and non-blocking and the index stores no state for such transactions. We show that LSTP ensures no missed dependencies between transactions and guarantees basic consistency for read-only transactions when update transactions are serializable. The design of LSTP and its provable properties is a proof of concept that P2P systems can be augmented with transactional semantics. Results from a preliminary simulation study are also presented.

REFERENCES

• 1: Atul Adya , Barbara H. Liskov, Weak consistency: a generalized theory and optimistic implementations for distributed transactions, Massachusetts Institute of Technology, 1999
• 2: Amazon simple storage service. http://www.amazon.com/gp/browse.html?node=16427261.
• 3: Luiz André Barroso , Jeffrey Dean , Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, v.23 n.2, p.22-28, March 2003 [doi>10.1109/MM.2003.1196112]
• 4: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 5: Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, ACM SIGMOD Record, v.24 n.2, p.1-10, May 1995
• 6: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 7: Adam Bosworth, Database issues for the 21st century, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066255]
• 8: A. Chan , R. Gray, Implementing Distributed Read-Only Transactions, IEEE Transactions on Software Engineering, v.11 n.2, p.205-212, February 1985 [doi>10.1109/TSE.1985.232196]
• 9: Adina Crainiceanu , Prakash Linga , Ashwin Machanavajjhala , Johannes Gehrke , Jayavel Shanmugasundaram, P-ring: an efficient and robust P2P range index structure, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247507]
• 10: F. Dabek. Cooperative File System. PhD thesis, Massachusetts Institute of Technology, September 2001.
• 11: Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable, ACM Transactions on Database Systems (TODS), v.30 n.2, p.492-528, June 2005 [doi>10.1145/1071610.1071615]
• 12: Bugra Gedik , Ling Liu, PeerCQ: A Decentralized and Self-Configuring Peer-to-Peer Information Monitoring System, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.490, May 19-22, 2003
• 13: Google alerts. http://www.google.com/alerts.
• 14: Abhishek Gupta , Ozgur D. Sahin , Divyakant Agrawal , Amr El Abbadi, Meghdoot: content-based publish/subscribe over P2P networks, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 15: R. Huebsch, B. Chun, J. Hellerstein, B. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. Yumerefendi. The architecture of pier: an internet-scale query processor. In CIDR, 2005.
• 16: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 17: Prakash Linga , Adina Crainiceanu , Johannes Gehrke , Jayavel Shanmugasudaram, Guaranteeing correctness and availability in P2P range indices, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066195]
• 18: David Lomet, Replicated indexes for distributed data, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.108-119, December 18-20, 1996, Miami Beach, Florida, United States
• 19: Nancy A. Lynch , Dahlia Malkhi , David Ratajczak, Atomic Data Access in Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.295-305, March 07-08, 2002
• 20: Dushyanth Narayanan , Austin Donnelly , Richard Mortier , Antony Rowstron, Delay aware querying with seaweed, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 21: 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
• 22: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 23: Jayavel Shanmugasundaram , Arvind Nithrakashyap , Rajendran Sivasankaran , Krithi Ramamritham, Efficient concurrency control for broadcast environments, ACM SIGMOD Record, v.28 n.2, p.85-96, June 1999
• 24: Mudhakar Srivatsa , Ling Liu, Vulnerabilities and Security Threats in Structured Overlay Networks: A Quantitative Analysis, Proceedings of the 20th Annual Computer Security Applications Conference, p.252-261, December 06-10, 2004 [doi>10.1109/CSAC.2004.50]
• 25: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.149-160, October 2001
• 26: C. Türker, K. Haller, C. Schuler, and H. Schek. How can we support grid transactions? towards peer-to-peer transaction processing. In CIDR, 2005.
• 27: William E. Weihl, Distributed Version Management for Read-Only Actions, IEEE Transactions on Software Engineering, v.13 n.1, p.55-64, January 1987 [doi>10.1109/TSE.1987.232835]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems