Space- and time-adaptive nonblocking algorithms

Details Space- and time-adaptive nonblocking algorithms Space- and time-adaptive nonblocking algorithms

2008-07-01

2008-07-01

Bullock, Jr., Lewis A. (Department: 2195)

Data processing: database and file management or data structures

Database design

Data structure types

C719S315000, C719S312000

Reexamination Certificate

active

07395274

ABSTRACT:
We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.

REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5081572 (1992-01-01), Arnold
patent: 5222238 (1993-06-01), Zobre et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Olivier
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: 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: 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
U.S. Appl. No. 09/547,288, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/547,290, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/710,218, filed Nov. 10, 2000 and naming as inventor(s) Harris, Timothy.
U.S. Appl. No. 09/837,671, filed Apr. 18, 2001 and naming as inventor(s) Detlefs et al.
Afek, Yehuda et al., “Long-Lived Renaming Made Adaptive”, 18thAnnual ACM Symposium on Principles of Distributed Computing, pp. 91-104, 1999.
Afek, Yehuda, “Wait-Free Made Fast”, 27thAnnual ACM Symposium on Theory of Computing, pp. 538-547, 1995.
Agesen, Ole et al., “DCAS-Based Concurrent Deques”, 12thAnnual ACM Symposium on Parallel Algorithms and Architectures, pp. 137-146, Jul. 2000.
Anderson, James H. et al., “Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations”, 12thAnnual ACM Symposium on Principles of Distributed Computing, Nov. 1995 (revised 1996, 1997).
Arora, Nimar S. et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, 10thAnnual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, 1998.
Attiya, Hagit et al., “An Adaptive Collect Algorithm with Applications”, Dept. of Computing Science, The Technion, Israel, May 10, 2001.
Barnes, Greg, “A Method for Implementing Lock-Free Shared Data Structures”, 5thAnnual ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, 1993.
Bayer, R. et al., “Concurrency of Operations on B-Trees”, Acta Informatica, 1977.
Detlefs, David L. et al., “Even Better DCAS-Based Concurrent Deques”, 14thInternational Conference on Distributed Computing, pp. 59-73, 2000.
Detlefs, David L. et al., “Lock-Free Reference Counting”, 20thAnnual ACM Symposium on Principles of Distributed Computing, pp. 190-199, 2001.
Dice, David et al., “Mostly Lock-Free Malloc”, ACM 2002.ACM Sigplan International Symposium on Memory Management, Jun. 2002.
Greenwald, Michael B., “Non-Blocking Synchronization and System Design”, PhD Thesis, Stanford University Technical Report STAN-CS-TR-1624, Palo Alto, California, Aug. 1999.
Herlihy, Maurice, “A Methodology for Implementing Highly Concurrent Data Objects”, ACM Transactions on Programming Languages and System, pp. 745-770, Nov. 1993.
Herlihy, Maurice, “Dynamic-Sized Lockfree Data Structures”, Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Transactions on Programming Languages and Systems, pp. 463-492, Jul. 1990.
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., “Transactional Memory: Architectural Support for Lock-Free Data Structures”, 20thInternational Symposium in Computer Architecture, 1993.
Herlihy, Maurice et al., “Obstruction-Free Synchronization: Double-Ended Queues as an Example”, 23rdInternational Conference on Distributed Computing, May 2003.
Israeli, Amos et al., “Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives”, 13thAnnual ACM Symposium on Principles of Distributed Computing, pp. 151-160, 1994.
Lamport, Leslie, “How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs”, IEEE Transactions on Computers, Sep. 1979.
Luchangco, Victor et al., “Nonblocking k-compare-single-swap”, 15thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jun. 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, Mar. 1997.
Michael, Maged M. et al., “Simple, Fast and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, 15thAnnual ACM Symposium on Principles of Distributed Computing, pp. 267-276, 1996.
Michael, Maged M., “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes”, 21stAnnual ACM Symposium on Principles of Distributed Computing, pp. 21-30, Jan. 2002.
Moir, Mark, “Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions”, 19thAnnual ACM Symposium on Principles of Distributed Computing, 2000.
Moir, Mark, “Practical Implementations of Non-Blocking Synchronization Primitives”, 16thAnnual ACM Symposium on Principles of Distributed Computing, 1997.
Moir, Mark, “Transparent Support for Wait-Free Transactions”, 11thInternational Workshop on Distributed Algorithms, 1997.
Moir, Mark et al., “Wait-Free Algorithms for Fast, Long-Lived Renaming”, Science of Computer Programming, Aug. 1994.
Saks, Michael et al., “Optimal Time Randomized Consensus—Making Resilient Algorithms Fast in Practice”, 2ndACM SIAM Symposium on Discrete Algorithms, pp. 351-362, 1991.
Shavit, Nir et al., “Software Transactional Memory”, Distributed Computing, Special Issue (10), 1997.
Trieber, R, “Systems Programming: Coping with Parallelism”, IBM Technical Report RJ5118, Apr. 23, 1986.
Turek, John et al., “Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking”, 11thACM Sigact-Sigmod-Sigart Symposium on Principles of Database Systems, 1992.
Agesen, Ole et al., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization,” ACM Sigplan N

Affiliated with

Also associated with

Rating

Space- and time-adaptive nonblocking algorithms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Space- and time-adaptive nonblocking algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space- and time-adaptive nonblocking algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2809506