Decentralized weighted voting for P2P data management

ABSTRACT

This paper presents a decentralized variant of David Gifford's classic weighted-voting scheme for managing replicated data. Weighted voting offers a familiar consistency model and supports on-line replica reconfiguration. These properties make it a good fit for applications in the pervasive computing domain. By distributing versioned metadata along with data replicas, and managing access to both data and metadata with the same quorums, our algorithm supports a peer-to-peer environment with dynamic device membership. Our algorithm has been implemented as part of a database called Oasis that was designed for pervasive environments.

REFERENCES

• 1: Daniel Barbará , Hector Garcia-Molina, Replicated Data Management in Mobile Environments: Anything New Under the Sun?, Proceedings of the IFIP WG10.3 Working Conference on Applications in Parallel and Distributed Computing, p.237-246, April 18-22, 1994
• 2: Y. Amir , A. Wool, Evaluating quorum systems over the Internet, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.26, June 25-27, 1996
• 3: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 4: Support for Speculative Update Propagation and Mobility in Deno, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.509, April 16-19, 2001
• 5: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: Guide, http://seattleweb.intel-research.net/projects/guide/, visited March 2003.
• 7: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 8: Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588061]
• 9: Holliday, J., Steinke, R., Agrawal, D., and Abbadi, A. E., Epidemic Quorums for Managing Replicated Data. 19th IEEE Intl. Performance, Computing, and Communications Conf 2000.
• 10: Peter J. Keleher, Decentralized replicated-object protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301345]
• 11: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 12: 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
• 13: LaMarca, A., Rodrig, M. Oasis: An Architecture for Simplified Data Management and Disconnected Operation, Intel Research Seattle Technical Report IRS-TR-03-003, May. 23, 2003.
• 14: Lamport, L. How to make a multiprocessor computer that correctly executes multiprocessor programs. IEEE Trans. on Computers, 28(9):690--691, Sept. 1979.
• 15: Rain, http://seattleweb.intel-research.net/projects/rain/, visited May 2003.
• 16: 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
• 17: Sweeney, A. et al, Scalability in the XFS File System. In Proc. of the 1996 Winter USENIX, 1996, 1--14.
• 18: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 19: Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France
• 20: Yang, B., and Garcia-Molina, H. Designing a Super-Peer Network. Tech Report, Stanford University, February 2002.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Management

Keywords:
consistency, peer-to-peer data management, pervasive computing, quorums, weighted voting