Shared synchronized skip-list data structure and technique...

Details Shared synchronized skip-list data structure and technique... Shared synchronized skip-list data structure and technique...

2003-09-03

2008-09-09

Cottingham, John (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07424477

ABSTRACT:
A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.

REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 5081572 (1992-01-01), Arnold
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Oliver
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 7117502 (2006-10-01), Harris
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2003/0182465 (2003-09-01), Moir et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 2008/0109608 (2008-05-01), Shavit et al.
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
patent: WO 01/53942 (2001-07-01), None
patent: WO 01/53943 (2001-07-01), None
patent: WO 01/80015 (2001-10-01), None
patent: WO 01/82057 (2001-11-01), None
patent: WO 03/060705 (2003-07-01), None
patent: WO 03/060715 (2003-07-01), None
Anderson, James H. et al., “Universal Constructions for Large Objects,”IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp. 1317-1332, 1999.
Harris, T., et al., “Language Support for Lightweight Transactions,”Proc. 18th Annual ACM SIGPLAN Conf. on Object-Oriented Programming Systesm, Languages, and Applications, pp. 388-402, ACM Press, New York, NY, 2003.
Herlihy, Maurice, “Dynamic-Sized Lockfree Data Structures,” Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized Lock-Free Data Structures,” Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “Obstruction-Free Synchronization: Double-Ended Queues as an Example,”Proceedings of the 23rd International Conference on Distributed Computing, p. 522, IEEE Computer Society, Washington, D.C., 2003.
Jayanti, P., et al., “Efficient and Practical Constructions of LL/SC Variables,”Proceedings of the 22nd Annual ACM Symposium on the Principles of Distributed Computing, pp. 285-294, ACM Press, New York, NY, 2003.
Martin, Paul et al., “DCAS-Based Concurrent Deques Supporting Bulk Allocation,” Sun Microsystems, Inc. Technical Report SMI TR-2002-111, Oct. 2002.
Michael, Maged M. et al., “Non-Blocking Algorithms and Preemption Safe Locking on Multiprogrammed Shared Memory Multiprocessors,”Journal of Parallel and Distributed Computing, vol. 51, No. 1, pp. 1-26, May 25, 1998.
Michael, Maged M. et al., “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,”Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing, pp. 21-30, ACM Press, New York, NY, 2002.
Prakash, Sundeep et al., “Non-Blocking Algorithms for Concurrent Data Structures,” Technical Report 91-002, University of Florida, Jul. 1, 1991 [URL: http://citeseer.ist.psu.edu/prakash91nonblocking.html].
Prakash, Sundeep et al., “A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap,”IEEE Transactions on Computers, vol. 43, No. 5, pp. 548-559, May 1994.
Shann, Chien-Hua et al., “A Practical Nonblocking Queue Algorithm Using Compare-and Swap,”Proceedings of the Seventh International Conference on Parallel and Distributed Systemsp. 470, IEEE Computer Society, Washington, D.C., 2000.
Shavit, N., et al., “Elimination Trees and the Construction of Pools and Stacks,”Theory of Computing Systems, vol. 30, pp. 645-670, 1997.
Shavit, N., et al., “Software Transactional Memory,”Distributed Computing, vol. 10, No. 2, pp. 99-116, Feb. 1997.
Valois, John D., “Lock-Free Linked Lists Using Compare-and-Swap,”Proceedings of the Fourteenth ACM Symposium on Principles of Distributed Computing, pp. 214-222, ACM Press, New York, NY 1995.
Herlihy, M.P., et al., “Linearizability: A Correctness Condition For Con-Current Objects,”ACM Transactions On Programming Languages and Systems, 12(3):463-492, Jul. 1990.
Herlihy, M.P., “Wait-Free Synchronization,”ACM Transactions On Programming Languages and Systems, 11(1):124-149, Jan. 1991.
Massalin, H., et al., “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991, 21 pages.
Massalin, Henry, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 158 pages, 1992 [retrieved from the Internet on Jul. 13, 2001: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Bershad, B. N., “Practical Considerations For Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273. IEEE Computer Society Press, Washington, D.C., 1993.
Herlihy, M., “A Methodology For Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, Hagit, et al., “Are Wait-Free Algorithms Fast?”Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, A., “A performance evaluation of lock-free synchronization protocols,”Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, New York, NY, 1994.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., et al., “The Synergy Between Non-Blocking Synchronization And Operating System Structure,”Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Arora, N. S., et al., “Thread Scheduling For Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, ACM Press, New York, NY, 1998.
Attiya, Hagit, et al., “Atomic Snapshots In O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, Aug. 1999, 241 pages.
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,”SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 134 146, ACM Press, New York, NY, ISBN: 1-58113-185-2, 2000.
Detlefs, David L., et al., “Even Better

Affiliated with

Also associated with

Rating

Shared synchronized skip-list data structure and technique... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Shared synchronized skip-list data structure and technique..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared synchronized skip-list data structure and technique... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3970331