Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2007-10-23
2007-10-23
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C707S793000, C707S793000
Reexamination Certificate
active
10674942
ABSTRACT:
One embodiment of the present invention provides a system that implements a hash table that is fully dynamic and lock-free. During a lookup in the hash table the system first uses a hash key to lookup a bucket pointer in a bucket array. Next, the system follows the bucket pointer to a data node within a linked list that contains all of the data nodes in the hash table, wherein the linked list contains only data nodes and at most a constant number of dummy nodes. The system then searches from the data node through the linked list to locate a node that matches the hash key, if one exists.
REFERENCES:
patent: 5671446 (1997-09-01), Rakity et al.
patent: 5960434 (1999-09-01), Schimmel
patent: 6067547 (2000-05-01), Doucceur
patent: 6654773 (2003-11-01), Hills
patent: 2001/0042204 (2001-11-01), Blaker et al.
patent: 2004/0107227 (2004-06-01), Michael
Maged, Michael M., “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets,” Aug. 2002, ACM Press.
Shalev, Ori and Nir Shavit, “Split-Ordered Lists: Lock-Free Extensible Hash Tables,” Jul. 13-16, 2003, ACM Press.
Harris, Timothy L., “A Pragmatic Implementation of Non-Blocking Linked-Lists,” Oct. 2001, Proceedings of the 15th International Symposium on Distributed Computing.
Publication entitled “Current Set Manipulation Without Locking”, by Vladimir Lanin et al., 7th ACM Symposium on the Principles of Database Systems, pp. 211-220, Mar. 1988.
Publication entitled “DCAS-Based Concurrent Deques”, by Ole Agesen et al., 12thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 2000.
Publication entitled “Dynamic Lock-Free Deques Using Single-Address Double-Word CAS”, by Maged M. Michael, Annual ACM Symposium on Principles of Distributed Computing Proceedings of the twenty-first annual Symposium on Principles of distributed computing, session 1, pp. 24-30, 2002, ISBN:1-58113-485.1.
Publication entitled “A Lock-Free Mechanism for Supporting Dynamic-Sized Data Structures”, Maurice Herlihy et al., Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Jul. 2003.
Publication entitled “Trie Hashing With Controlled Load”, by Witold A. Litwin et al., IEEE Transactions on Software Engineering, vol. 17, No. 7, Jul. 1991.
Publication entitled “Split-Ordered Lists—Lock-free Resizable Hash Tables”, by Ori Shalev et al., Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, pp. 102-111, Jul. 13-16, 2003, Boston Massachusetts.
Publication entitled “The Repeat Offender Problem: A Lock-Free Mechanism for Supporting Dynamic-Sized Data Structures”, by Maurice Herlihy et al., SUN Microsystems, Inc., Report TR-2002, 112, Jul. 2002.
Publication entitled “A Pragmatic Implementation of Non-Blocking Linked-Lists”, by Timothy L. Harris, Proceedings of the 15thInternational Symposium on Distributed Computing, Oct. 2001, pp. 300-314.
Publication entitled “Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors”, by Maged M. Michael, Journal of Parallel and Distributed Computing 51(1), pp. 1-26, 1998..
Publication entitled “Non-Blocking K-Compare-Single-Swap” by Victor Luchangco et al., Sun Microsystems Laboratories 1 Network Drive Burlington, MA 01803, USA research.sun.com/projects/scalable/ Papers/p004-luchangco.pdf.
Publication entitled “Concurrent Maintenance of Skip Lists”, by William Pugh Department of Computer Science, University of Maryland, CS-TR-2222.1, Jun. 1990..
Publication entitled “Skiplist-Based Concurrent Priority Queues”, By I. Lotan Annual ACM Symposium on Principles of Distributed Computing, pp. 113-122, Atlanta, GA, May 1999.
Publication entitled “Non-Blocking Timeout in Scalable Queue-Based Spin Locks”, by Michael L. Scott, F Department of Computer Science, University of Rochester, Feb. 2002.
Publication entitled “Trie Hashing”, by Witold Litwin, 1981 ACM 0-89791-090-0, pp. 19-29.
Publication entitled “Linear Hashing: A New Tool for File and Table Addressing”, by Withold A. Litwin, Proceedings of the Sixth Conference on Very Large Data Bases, 1980, pp. 212-223. http://www.ccom.unh.edu/vislab/cs515/Linear%20 Hashing.htm.
Publication entitled “Lock-Free Linked Lists Using Compare-and-Swap”, by John D. Valois, Symposium on Principles of Distributed Computing 1995, pp. 214-222..
Publication entitled “Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations”, by James H. Anderson et al., Distributed Computing, 11(1):1-20, Sep. 1997.
Publication entitled “Practical Implementations of Non-Blocking Synchronization Primitives” by Mark Moir, Proceedings of the 15thAnnual ACM Symposium on the Principles of Distributed Computing, Aug. 1997.
Luchangco Victor
Maessen Jan-Willem
Martin Paul A.
Rutz Jared I
Sparks Donald
LandOfFree
Method and apparatus for implementing a fully dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing a fully dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a fully dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3860119