Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-12-19
2006-12-19
Gaffin, Jeffrey (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C714S006130
Reexamination Certificate
active
07152077
ABSTRACT:
Data structure and timestamp management techniques for redundant storage. A plurality of storage devices are interconnected by a communication medium. At least two of the storage devices are designated devices for storing a block of data. Each designated device stores a version of the data and a first timestamp that is indicative of when the version of data was last updated. A second timestamp is indicative of a pending update to the block of data. When the update to the block of data is completed at one of the designated devices, the device discards the second timestamp. A storage device acting as coordinator instructs the device to discard the second timestamp. The designated storage devices store a plurality of blocks of data and corresponding timestamps according to a data structure. At least some of the entries in the data structure correspond to a range of data blocks that share a common timestamp. Entries in the data structure are arranged such that the ranges do not overlap.
REFERENCES:
patent: 4714996 (1987-12-01), Gladney et al.
patent: 5212788 (1993-05-01), Lomet et al.
patent: 5430869 (1995-07-01), Ishak et al.
patent: 5452445 (1995-09-01), Hallmark et al.
patent: 5504900 (1996-04-01), Raz
patent: 5546582 (1996-08-01), Brockmeyer et al.
patent: 5644763 (1997-07-01), Roy
patent: 5701480 (1997-12-01), Raz
patent: 5768538 (1998-06-01), Badovinatz et al.
patent: 5799305 (1998-08-01), Bortvedt et al.
patent: 5920857 (1999-07-01), Rishe et al.
patent: 5953714 (1999-09-01), Abdullah
patent: 6052712 (2000-04-01), Badovinatz et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6219667 (2001-04-01), Lu et al.
patent: 6421688 (2002-07-01), Song
patent: 2005/0108302 (2005-05-01), Rand et al.
patent: 1160682 (2001-05-01), None
Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, Michael Williams, Replication in the Harp File System, Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, Oct. 13-16, 1991, Asilomar Conference Center, Pacific Grove, CA, pp. 226-238, ACM Press, New York, 1991.
Edward K. Lee, Chandramohan A. Thekkath, Petal: Distributed Virtual Disks, ASPLOS-VII Proceedings / Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, Massachusetts, Oct. 1-5, 1996, pp. 84-92, ACM Press, New York, 1996.
Leslie Lamport, The Part-Time Parliament, ACM Transactions on Computer Systems, vol. 16, No. 2, pp. 133-169, ACM Press, New York, 1998.
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Sharing Memory Robustly in Message-Passing Systems, Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing: Quebec City, Quebec, Canada, Aug. 22-24, 1990, pp. 363-375, ACM Press, New York, 1990.
Nancy A. Lynch, Alexander A. Shvartsman, Robust Emulation of Shared Memory using Dynamic Quorum-Acknowledged Broadcasts, International Symposium on Fault-Tolerant Computing 1997: Seattle, Washington, pp. 272-281, IEEE Computer Society Press, Los Alamitos, 1997.
Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter, Decenteralized Storage Consistency via Versioning Servers, Carnegie-Mellon University Technical Report CMU-CS-02-180 Carnegie-Mellon University, ECE Department, Pittsburgh, Sep. 2002. < http://www.pdl.cmu.edu/PDL-FTP/PASIS/CMU-CS-02-180.pdf>.
Khalil Amiri, Garth Gibson, Richard Golding, Highly Concurrent Shared Storage, 20th International Conference on Distributed Computing Systems: proceedings: Taipei, Taiwan, Apr. 10-13, 2000, pp. 298-307, IEEE Computer Society, Los Alamitos, 2000.
Hans-Peter Kriegel, Marco Potke, Thomas Seidl, Managing Intervals Efficiently in Object-Relational Databases, Marking the millennium: 26th International Conference on Very Large Databases, Cairo, Egypt, Sep. 10-14, 2000, pp. 407-418, Morgan Kaufmann, Orlando, 2000.
Steven Berson, R. R. Muntz, W. R. Wong, Randomized Data Allocation for Real-time Disk I/O, Digest of papers: Compcon '96; technologies for the information superhighway, Feb. 25-28, 1996, Santa Clara, CA, pp. 286-290, IEEE Computer Society, Los Alamitos, 1996.
Steven Hand, Timothy Roscoe, Mnemosyne: Peer-to-Peer Steganographic Storage, Peer-to-peer systems: First International Workshop, IPTPS 2002, Cambridge, MA, USA, Mar. 7-8, 2002: revised papers, Springer, New York, 2002.
Hui-I Hsiao, Chained Declustering: A New Availability Strategy for Multiprocessor Database machines, Data engineering: proceedings / Sixth International Conference on Data Engineering, Feb. 5-9, 1990, Los Angeles Airport Hilton and Towers, Los Angeles, California, USA, pp. 456-465, IEEE Computer Society Press, Los Alamitos, 1990.
Arif Merchant, Phillip S. Yu, Analytic modeling of Clustered RAID with Mapping Based on Nearly Random Permutation, IEEE transactions on Computers, vol. 45, No. 3, Mar. 1996, pp. 367-373, IEEE Computer Society Press, Los Alamitos, 1996.
Gabriel Mizrahi, The Hashing Approch to the Internet File System Problem, M. A. Thesis, Department of Mathematics, University of Hafia, Isreal, Nov. 2001.
Jose Renato Santos, R. R. Muntz, B. Ribeiro-Neto, Comparing Random Data Allocation and Data Striping in Multimedia Servers, Proceedings ACM SIGMETRIC '2000: International Conference on Measurement and Modeling of Computer Systems, Jun. 17-21, 2000, Santa Clara, CA, USA, pp. 44-55 ACM Press, New York, 2000.
Avishai Wool, Quorum Systems in Replicated Databases: Science or Fiction?, Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol. 21, No. 4, Dec. 1998, pp. 3-11, IEEE Computer Society Press, Los Alamitos, 1998.
Robert H. Thomas, A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases, ACM Transactions on Database Systems (TODS), vol. 4, No. 2, Jun. 1979, pp. 180-209, ACM Press, New York, 1979.
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Sharing memory robustly in message-passing systems, vol. 42, No. 1, Jan. 1995, pp. 124-142, Journal of the ACM (JACM), ACM Press, New York, 1995.
Frolund Svend
Merchant Arif
Saito Yasusuhi
Spence Susan
Veitch Alistair
Gaffin Jeffrey
Hewlett--Packard Development Company, L.P.
Pyo Monica
LandOfFree
System for redundant storage of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for redundant storage of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for redundant storage of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3668849