Pith. sign in

REVIEW 4 major objections 5 minor 67 references

Reciprocating Locks

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Reciprocating Locks is a mutual exclusion algorithm with a constant-time doorway arrival phase and release, a single thread-local waiting element per thread, bounded bypass, and lower coherence traffic than MCS and CLH under sustained…

desk verdict A genuinely new lock algorithm with constant-time paths and local spinning; correctness rests on an unproven marker invariant, but the paper deserves review. read the letter →

arxiv 2501.02380 v10 pith:PA3HNSOA submitted 2025-01-04 cs.DC

Dave Dice , Alex Kogan This is my paper · ORCID
classification cs.DC
keywords SynchronizationLocksMutualExclusionMutexScalabilityCache-coherentSharedMemorylocalspinningboundedbypass
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces Reciprocating Locks, a mutual exclusion algorithm for cache-coherent shared memory that pursues a combination of properties existing locks do not fully offer: a constant-time doorway arrival phase, a constant-time release, local spinning, a single thread-local waiting element regardless of how many locks a thread holds, bounded bypass, and freedom from starvation. The authors' central claim is that these properties can be had without strict FIFO admission by splitting waiters into an arrival stack and an entry segment and by treating a thread's own element address as a zombie end-of-segment marker. If the claim is right, it matters because MCS and CLH, the standard scalable queue locks, carry queue-node lifecycle overhead and non-constant release paths, while Reciprocating Locks is compact enough for kernel, pthread, or C++ use and, in the paper's measurements, generates less coherence traffic and equal or better throughput under sustained contention.

What carries the argument

The central object is the arrival word, a single atomic pointer encoding the unlocked state, the locked-with-empty-arrival-segment state, or a stack of waiting elements. Arriving threads atomically exchange their thread-local wait element address into that word, and the value returned is their successor on the implicit stack. The load-bearing mechanism is the end-of-segment sentinel carried in the Gate field of each wait element: when a segment is detached, the address of the original owner's element travels down the chain, and each successor compares its own successor pointer against this address to detect the logical terminus without dereferencing a dead element. That address comparison is what lets a single per-thread element serve simultaneously as a live waiter and as a buried zombie marker.

What would settle it

A model checker or a directed stress test with three threads, two locks, and a singleton element per thread could settle it: if any schedule makes the end-of-segment comparison in Listing 1 fire for a successor that is not the actual segment terminus, a waiting thread is skipped and the lock's progress guarantee fails. Exhaustively searching the interleavings of the atomic exchange, CAS, and Gate stores for that state is the direct falsifier.

Watch

Extended reading notes

Core claim

Under contention, Reciprocating Locks keeps waiting threads in two stacks: an arrival segment, onto which arriving threads push their wait elements with a single atomic exchange, and an entry segment, through which ownership passes by direct thread-to-thread stores to a Gate flag. The release operation detaches the whole arrival segment only when the entry segment is exhausted, so each acquire and release path is constant time. The trick that makes a single per-thread element safe is the zombie terminal: the address of a thread's element, even after that thread has been admitted, is propagated through the entry segment as an end-of-segment marker and recognized by an address comparison rather than by dereferencing the element. The paper argues this yields bounded bypass (a thread can be overtaken at most once per segment population), local spinning, four coherence invalidations per contended episode versus five for CLH, and throughput at or above MCS, CLH, TWA, HemLock, and ticket locks in its MutexBench, std::atomic, and LevelDB experiments.

Load-bearing premise

The whole algorithm's correctness rests on the assumption that a thread's waiting-element address, when used only as an end-of-segment marker, can never be confused with a live successor by the pointer comparison in the handoff loop; the paper supports this with scenario analysis rather than a formal invariant proof or exhaustive model check.

Editorial extensions

If this is right

  • A pthread mutex or kernel spinlock built from Reciprocating Locks can be released without waiting for successor acknowledgement, so lock and unlock remain bounded operations even under contention.
  • Because the waiting element is a thread-local singleton, a thread holding dozens of locks, as the Linux kernel's lockdep anticipates, needs one element per thread rather than one per lock, eliminating the queue-node allocation and free paths of MCS.
  • The bounded-bypass guarantee means no thread can be overtaken more than once by each other contending thread per segment, so indefinite starvation is excluded even though admission is not FIFO.
  • Under sustained contention the lock touches the shared arrival word only when a segment boundary is crossed, so coherence traffic per acquire-release episode stays constant and independent of thread count.
  • The palindromic admission schedule that emerges from LIFO-within-segment, FIFO-between-segments ordering can give a two-to-one admission disparity over long runs, but the paper argues it improves aggregate last-level cache residency relative to pure FIFO.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension the paper leaves implicit is that the same two-segment, zombie-marker design should compose with OS sleep-waiting primitives such as futex or park-unpark, because the constant-time doorway means a thread waits on exactly one condition; a testable version would replace the pause loop with a futex wait on the Gate field and measure wakeup latency under oversubscription.
  • The appendix's retrograde ticket lock shows the admission policy is separable from the exchange-based stack, so systems without a wait-free exchange could implement the same bounded-bypass, constant-time-release behavior with fetch-and-add ticket counters.
  • The cache-residency argument for palindromic schedules suggests a broader testable conjecture: any non-FIFO admission policy that alternates between forward and reverse order will beat round-robin FIFO on aggregate last-level-cache miss rate, which could be benchmarked independently with a synthetic scheduler controlling admission order directly.
  • Because the correctness of the zombie marker rests on address comparison rather than dereference, a production implementation should pin wait elements in thread-local storage and document that element addresses must remain stable for the thread's lifetime, since reused or recycled stack addresses could turn latent undefined behavior into a live bug.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces Reciprocating Locks, a spin lock for cache-coherent shared memory. The lock maintains an arrival stack of thread-local wait elements; an arriving thread atomically exchanges its element's address into the lock's Arrivals word, and if the lock is busy it spins on a Gate flag in its own element. On release, if an entry segment exists, ownership is passed through the segment by writing the end-of-segment marker into the successor's Gate field; otherwise the arrival segment is detached and becomes the new entry segment. The paper claims a constant-time doorway and release, local spinning, a single per-thread wait element, bounded bypass, strong anti-starvation properties, and lower coherence traffic than MCS and CLH under sustained contention. The authors provide a complete C++ implementation (Listing 1), informal scenario analyses (Section 4), a property comparison table (Table 1), and benchmark results on Intel x86 and ARMv8 (Section 7).

Significance. If the correctness and performance claims hold, Reciprocating Locks is a worthwhile practical contribution: it offers the constant-time release of CLH while using a stable per-thread singleton element like HemLock, and the experimental data suggest competitive throughput and low coherence traffic. The paper ships complete, runnable code and compares against external, non-fitted baselines (MCS, CLH, Ticket, TWA, HemLock), which is a clear strength. However, the central safety and liveness claims rest on an unproved invariant concerning the 'zombie' end-of-segment marker, and the performance claims would be materially strengthened by error bars or statistical tests. These are load-bearing issues, so the paper needs a major revision rather than acceptance in its current form.

major comments (4)
  1. [Section 4 and Listing 1, line 37] The correctness of the end-of-segment marker mechanism is not rigorously established. The paper asserts in Section 4 that the element whose address is used as a marker 'will not be subsequently accessed,' and the comparison at Listing 1 line 37 (`succ == eos`) is the load-bearing check that a waiting thread is not skipped. Because each thread uses a singleton TLS element, a thread that finishes one locking episode and immediately reacquires (possibly the same lock) can push that same element onto a new arrival segment while its address is still being propagated as the marker through an older entry segment. The informal scenario analysis in Section 4 covers several interleavings but does not prove that no interleaving, including plural locking and immediate reacquisition, can cause line 37 to mismatch a live successor. A formal invariant (or a model check) is needed to support the mutual-exclusion and lockout-freedom claims.
  2. [Section 2 and Listing 1, lines 20-41] The paper gives no formal proof of mutual exclusion, progress, or bounded bypass. The claim that the lock is held exactly when the Arrivals word is non-zero, and that only one thread can be in the critical section, is supported only by narrative scenarios. In particular, the transition from the waiting loop at lines 29-33 to the critical section at line 47, and the subsequent release logic, rely on the invariant that a thread seeing a non-null Gate value is the unique owner. Given that the paper makes strong liveness guarantees (bounded bypass, anti-starvation), a rigorous inductive invariant or a proof in a recognized concurrency framework is required.
  3. [Section 7 and Figure 1] The performance results are reported as medians of 7 runs without error bars, confidence intervals, or statistical tests. The paper's headline claims that Reciprocating Locks 'provides the best throughput' and 'generates less coherence traffic than MCS and CLH' (Abstract, Section 7.1) would be substantially more convincing with an indication of run-to-run variability. This is especially important for the coherence-traffic metric in Table 1, which is approximated from a single hardware counter (`l2d_cache_inval`) on one ARMv8 system; the authors should state the variance and the number of runs for the counter measurements.
  4. [Appendix B and Section 4] The discussion of on-stack allocation of wait elements introduces a correctness concern that is not resolved. Appendix B acknowledges that using an address of an out-of-scope stack object as an end-of-segment marker is undefined behavior in C++, and that on-stack allocation is safe only under assumptions about the thread model. The paper's abstract and Section 4 claim that a single per-thread waiting element suffices; the clean version of this claim requires TLS storage with lifetime equal to the thread. The on-stack discussion should be clearly separated from the main algorithm or removed, and the TLS version's lifetime invariant should be stated precisely.
minor comments (5)
  1. [Section 4, step 8] Typo: 'critcal' should be 'critical'.
  2. [Table 1 and Section 8] The 'Context-free' column in Table 1 lists Reciprocating as 'No', but Section 8 explains that context can be passed via TLS or RAII wrappers; the table's classification of CLH and MCS as also non-context-free is consistent, but the distinction between 'context required' and 'context can be supplied out-of-line' should be clarified.
  3. [Appendix D] Typos: 'legay' should be 'legacy', and 'accomodate' should be 'accommodate'.
  4. [Throughout] The manuscript contains numerous informal editorial insertions, such as naming candidates, 'UB; Nasal Demons', and 'halt-and-catch-fire'. These are inappropriate for a published paper and should be removed or moved to a technical report.
  5. [Section 7, LevelDB] The LevelDB experiment compares only a single workload (readrandom with fixed 50-second runs on a populated database); a brief description of the database size and the time to populate would improve reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic properties are derived from code structure and performance claims are measured against external baselines.

full rationale

The paper's central claims are algorithmic and empirical rather than derived from fitted inputs. The constant-time doorway and release properties are established by direct inspection of Listing 1: the acquire path uses a single atomic exchange (line 20) and the release path uses at most a compare-and-swap (line 66) and an atomic exchange (line 73), each a bounded number of operations. The single-waiting-element property follows from the definition of the thread-local WaitElement E and the invariant that a thread waits on at most one lock at a time. The bounded-bypass and anti-starvation claims are consequences of the LIFO-within-arrival-segment / FIFO-between-segments structure described in Section 2, not of any fitted parameter or self-referential definition. Performance is evaluated against external baseline algorithms (MCS, CLH, Ticket, TWA, HemLock) using MutexBench, std::atomic microbenchmarks, and LevelDB; no parameter is fitted to the target data and then reported as a prediction. The paper does cite the authors' prior work (e.g., CNA, HemLock, TWA), but those citations supply implementation techniques and comparison points, not the load-bearing correctness or performance conclusions. The informal scenario analysis of the zombie end-of-segment marker at Listing 1 line 37 is a verification gap, not a circular derivation: the claim is asserted and illustrated, not derived from its own conclusion.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The algorithm relies on standard hardware atomicity assumptions and on the design convention that only the lock holder detaches the arrival segment. No free parameters are fitted to benchmark data; the performance claims are empirical.

assumptions (5)
  • domain assumption Atomic exchange and compare-exchange on pointer-sized values are wait-free on the target platforms.
    Section 3 states the implementation assumes wait-free std::atomic exchange/CAS, citing x86 and ARM LSE.
  • domain assumption Wait element addresses have low-order bit zero, enabling the LOCKEDEMPTY distinguished pointer encoding.
    Section 3 and Listing 1 require aligned wait elements so bit 0 is free for the one-value encoding.
  • domain assumption A thread waits on at most one lock at a time, so a singleton TLS wait element suffices.
    Section 2 states this to justify the single per-thread waiting element and bound memory use.
  • standard math Release/acquire memory ordering on Gate and Arrivals is sufficient for correct handoff.
    The implementation uses memory_order_release for stores to Gate and memory_order_acquire for loads; no formal memory-model proof is given, but this is standard practice.
  • ad hoc to paper The end-of-segment marker address is only compared, never dereferenced, even when it aliases a live element on another segment.
    Section 4's zombie terminal element description and Appendix B rely on this to allow address-based terminus detection without accessing the marked element; no proof is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reciprocating Locks." pith.science (2026). https://pith.science/paper/PA3HNSOA

@misc{pith2026250102380,
  author       = {Pith},
  title        = {Pith review of: Reciprocating Locks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PA3HNSOA}},
  note         = {Machine review of arXiv:2501.02380}
}
read the original abstract

We present "Reciprocating Locks", a novel mutual exclusion locking algorithm, targeting cache-coherent shared memory (CC), that enjoys a number of desirable properties. The doorway arrival phase and the release operation both run in constant-time. Waiting threads use local spinning and only a single waiting element is required per thread, regardless of the number of locks a thread might hold at a given time. While our lock does not provide strict FIFO admission, it bounds bypass and has strong anti-starvation properties. The lock is compact, space efficient, and has been intentionally designed to be readily usable in real-world general purpose computing environments such as the linux kernel, pthreads, or C++. We show the lock exhibits high throughput under contention and low latency in the uncontended case. The performance of Reciprocating Locks is competitive with and often better than the best state-of-the-art scalable spin locks.

Figures

Figures reproduced from arXiv: 2501.02380 by the authors.

Figure 1
Figure 1. MutexBench We ran the benchmark under the following lock algo￾rithms: MCS is classic MCS. To avoid memory allocation during the measurement interval, the MCS implementation uses a thread-local stack of free queue elements. CLH is CLH based on Scott’s CLH variant with a standard interface Figure￾4.14 of [53]; For the MCS and CLH locks, our implementa￾tion stores the current head of the queue – the owner – in a field … view at source ↗
Figure 2
Figure 2. C++ std::atomic<struct> 1 2 5 10 20 50 Threads 1.049 2.097 Aggregate Throughput in Mops/sec 1e6 TKT MCS CLH TWA HemLock Recipro [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. LevelDB : readrandom of such primitives allows the implementation to avoid toxic waiting policies, such as unbounded busy-waiting; periodic polling via timed sleep operations; or operating-system advi￾sory yield calls. Specifically, having constant-time paths means contending threads wait on only one condition – transfer of ownership – and have one waiting phase. In contrast, locks such as MCS or HemLock may need to… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Retrograde Ticket Locks in Action The classic ticket lock uses grant and ticket fields, where arriving threads atomically fetch-and-increment ticket and then wait for the assigned ticket value to equal grant and the corresponding Release operator increments grant. For …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 50 canonical work pages

  1. [1]

    Ole Agesen, David Detlefs, Alex Garthwaite, Ross Knippel, Y. S. Ra- makrishna, and Derek White. An efficient meta-lock for implementing ubiquitous synchronization.SIGPLAN Notices OOPSLA 1999, 1999. doi:10.1145/320385.320402

    work page arXiv 1999

  2. [2]

    Performance Prediction for Coarse-Grained Locking

    Vitaly Aksenov, Dan Alistarh, and Petr Kuznetsov. Performance pre- diction for coarse-grained locking.CoRR, abs/1904.11323, 2019. URL: http://arxiv.org/abs/1904.11323,arXiv:1904.11323

    work page Pith review arXiv 1904

  3. [4]

    Anderson and Yong-Jik Kim

    James H. Anderson and Yong-Jik Kim. An improved lower bound for the time complexity of mutual exclusion.Distrib. Comput., 2002. doi:10.1007/s00446-002-0084-2

    work page doi:10.1007/s00446-002-0084-2 2002

  4. [5]

    Anderson, Y.J

    J.H. Anderson, Y.J. Kim, and T. Herman. Shared-memory mutual exclusion: major research trends since 1986.Distributed Computing,

    work page 1986

  5. [6]

    T. E. Anderson. The performance of spin lock alternatives for shared- money multiprocessors.IEEE Transactions on Parallel and Distributed Systems, 1990.doi:10.1109/71.80120

    work page doi:10.1109/71.80120 1990

  6. [7]

    Tight RMR lower bounds for mutual exclusion and other problems

    Hagit Attiya, Danny Hendler, and Philipp Woelfel. Tight RMR lower bounds for mutual exclusion and other problems. InProceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, 2008.doi:10.1145/1374376.1374410

    arXiv 2008

  7. [8]

    Auslander, D

    M. Auslander, D. Edelsohn, O. Krieger, B. Rosenburg, and R. Wis- niewski. Enhancement to the MCS lock for increased functional- ity and improved programmability – U.S. patent application num- ber 20030200457, 2003. URL:https://patents.google.com/patent/ US20030200457

    work page 2003

  8. [9]

    Avis and M

    D. Avis and M. Newborn. On pop-stacks in series.Utilitas Math. 19, pages 129–140, 1981

    work page 1981

Show all 67 references
  1. [10]

    Cam- bridge university press, 2004

    Stephen Boyd and Lieven Vandenberghe.Convex optimization. Cam- bridge university press, 2004

    2004

  2. [11]

    A fair and space-efficient mutual exclusion

    Sheng-Hsiung Chen and Ting-Lu Huang. A fair and space-efficient mutual exclusion. In11th International Conference on Parallel and Distributed Systems (ICPADS’05), 2005. doi:10.1109/ICPADS.2005. 23

    2005 doi

  3. [12]

    Bounded-bypass mutual exclusion with minimum number of registers.IEEE Trans

    Sheng-Hsiung Chen and Ting-Lu Huang. Bounded-bypass mutual exclusion with minimum number of registers.IEEE Trans. Parallel Distrib. Syst., 2009.doi:10.1109/TPDS.2009.28

    2009 doi

  4. [13]

    A surprise with mutexes and reference counts

    Jonathan Corbet. A surprise with mutexes and reference counts. https://lwn.net/Articles/575460, December 4, 2013

    2013

  5. [14]

    MCS locks and qspinlocks.https://lwn.net/Articles/ 590243, March 11, 2014, 2014

    Jonathan Corbet. MCS locks and qspinlocks.https://lwn.net/Articles/ 590243, March 11, 2014, 2014. Accessed: 2018-09-12

    2014

  6. [15]

    Mcs locks and qspinlocks, 2014

    Jonathan Corbet. Mcs locks and qspinlocks, 2014. URL:https://lwn. net/Articles/590243/

    2014

  7. [16]

    Building FIFO and priority-queueing spin locks from atomic swap, 1993

    Travis Craig. Building FIFO and priority-queueing spin locks from atomic swap, 1993

    1993

  8. [17]

    Intel®Xeon®Processor Scalable Family Technical Overview, 2017

    Intel Corporation David Mulnix. Intel®Xeon®Processor Scalable Family Technical Overview, 2017. Updated 2022. URL:https://www.intel.com/content/www/us/en/developer/articles/ technical/xeon-processor-scalable-family-technical-overview.html

    2017

  9. [18]

    Malthusian locks.CoRR, abs/1511.06035, 2015

    Dave Dice. Malthusian locks.CoRR, abs/1511.06035, 2015. URL: http://arxiv.org/abs/1511.06035,arXiv:1511.06035

    2015 arXiv

  10. [19]

    Malthusian locks

    Dave Dice. Malthusian locks. InProceedings of the Twelfth European Conference on Computer Systems, EuroSys ’17, 2017. URL:http://doi. acm.org/10.1145/3064176.3064203

    2017

  11. [20]

    Avoiding scalability collapse by restricting concurrency

    Dave Dice and Alex Kogan. Avoiding scalability collapse by restricting concurrency. InEuro-Par 2019: Parallel Processing - 25th International Conference on Parallel and Distributed Computing, Göttingen, Germany, August 26-30, 2019, Proceedings, Lecture Notes in Computer Scienc...

    2019 doi

  12. [21]

    Compact NUMA-Aware Locks

    Dave Dice and Alex Kogan. Compact NUMA-Aware Locks. InProceed- ings of the Fourteenth EuroSys Conference 2019, EuroSys ’19. Association for Computing Machinery, 2019.doi:10.1145/3302424.3303984

    2019

  13. [22]

    TWA - ticket locks augmented with a waiting array

    Dave Dice and Alex Kogan. TWA - ticket locks augmented with a waiting array. InEuro-Par 2019: Parallel Processing - 25th International Conference on Parallel and Distributed Computing, Göttingen, Germany, August 26-30, 2019, Proceedings. Springer, 2019. doi:10.1007/978-3- 030-...

    2019 doi

  14. [23]

    Fissile locks, 2020

    Dave Dice and Alex Kogan. Fissile locks, 2020. URL:https://arxiv.org/ abs/2003.05025,arXiv:2003.05025

    2020 arXiv

  15. [24]

    Fissile locks

    Dave Dice and Alex Kogan. Fissile locks. InNetworked Systems (NETYS 2020), 2021. URL:https://doi.org/10.1007/978-3-030-67087-0_13

    2020 doi

  16. [25]

    Marathe, and Nir Shavit

    Dave Dice, Virendra J. Marathe, and Nir Shavit. Persistent unfairness arising from cache residency imbalance. InProceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, 2014. URL:https://doi.org/10.1145/2612669.2612703

    2014

  17. [26]

    Hemlock : Compact and scalable mutual exclusion

    David Dice and Alex Kogan. Hemlock : Compact and scalable mutual exclusion. InProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, 2021. URL:https://doi.org/10. 1145/3409964.3461805

    2021

  18. [27]

    Marathe, and Nir Shavit

    David Dice, Virendra J. Marathe, and Nir Shavit. Lock Cohorting: A General Technique for Designing NUMA Locks. InProceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12. Association for Computing Machinery, 2012. doi:10.1145/...

    2012

  19. [28]

    Marathe, and Nir Shavit

    David Dice, Virendra J. Marathe, and Nir Shavit. Lock Cohorting: A General Technique for Designing NUMA Locks.ACM Trans. Parallel Comput., 2015. URL:http://doi.acm.org/10.1145/2686884, doi:10.1145/2686884

    2015 doi

  20. [29]

    Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code

    Rotem Dvir and Gadi Taubenfeld. Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code. In James Asp- nes, Alysson Bessani, Pascal Felber, and João Leitão, editors,21st International Conference on Principles of Distributed Systems (OPODIS 2017), Leibn...

    2017 doi

  21. [30]

    Modeling Critical Sections in Am- dahl’s Law and Its Implications for Multicore Design

    Stijn Eyerman and Lieven Eeckhout. Modeling Critical Sections in Am- dahl’s Law and Its Implications for Multicore Design. InProceedings of the 37th Annual International Symposium on Computer Architec- ture, ISCA ’10. ACM, 2010. URL:http://doi.acm.org/10.1145/1815961. 1816011,...

  22. [31]

    M. J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin. Resource allocation with immunity to limited process failure. In20th Annual Symposium on Foundations of Computer Science (FOCS 1979), 1979. URL:http://dx.doi.org/10.1109/SFCS.1979.37

    1979 doi

  23. [32]

    Fuss, futexes and furwocks: Fast user-level locking in linux.https://www.kernel.org/ doc/ols/2002/ols2002-pages-479-495.pdf

    Hubertus Franke, Rusty Russel, and Matthew Kirkwood. Fuss, futexes and furwocks: Fast user-level locking in linux.https://www.kernel.org/ doc/ols/2002/ols2002-pages-479-495.pdf. Ottawa Linux Symposium

    2002

  24. [33]

    When Slower is Faster.CoRR,

    Carlos Gershenson and Dirk Helbing. When Slower is Faster.CoRR,

  25. [34]

    Lock–unlock: Is that all? a pragmatic analysis of locking in software systems.ACM Trans

    Rachid Guerraoui, Hugo Guiroux, Renaud Lachaize, Vivien Quéma, and Vasileios Trigonakis. Lock–unlock: Is that all? a pragmatic analysis of locking in software systems.ACM Trans. Comput. Syst., 2019. doi: 10.1145/3301501

    2019 doi

  26. [35]

    Hesselink and Peter A

    Wim H. Hesselink and Peter A. Buhr. MCSH, a Lock with the Standard Interface.ACM Trans. Parallel Comput., 2023. URL:https://doi.org/10. 1145/3584696

    2023

  27. [36]

    Towards an ideal queue lock

    Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. Towards an ideal queue lock. InProceedings of the 21st International Conference on Distributed Computing and Networking, ICDCN 2020. Association for Computing Machinery, 2020. URL:https://doi.org/10.1145/3369740. 3369784

    2020 doi

  28. [37]

    Simple, fast, scalable, and reliable multiprocessor algorithms

    Siddhartha Visveswara Jayanti. Simple, fast, scalable, and reliable multiprocessor algorithms. Massachusetts Institute of Technology,

  29. [38]

    Local-Spin Mutual Exclusion Algorithms on the DSM Model Using fetch&store Objects

    Hyonho Lee. Local-Spin Mutual Exclusion Algorithms on the DSM Model Using fetch&store Objects. Masters Thesis, University of Toronto. URL:http://www.cs.toronto.edu/pub/hlee/thesis.ps

  30. [39]

    Transformations of mutual exclusion algorithms from the cache-coherent model to the distributed shared memory model

    Hyonho Lee. Transformations of mutual exclusion algorithms from the cache-coherent model to the distributed shared memory model. In 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), 2005.doi:10.1109/ICDCS.2005.83

    2005 doi

  31. [40]

    Lockdoc: Trace-based analysis of locking in the linux kernel

    Alexander Lochmann, Horst Schirmeier, Hendrik Borghorst, and Olaf Spinczyk. Lockdoc: Trace-based analysis of locking in the linux kernel. InProceedings of the Fourteenth EuroSys Conference 2019, EuroSys ’19. Association for Computing Machinery, 2019. doi:10.1145/3302424. 3303948

    2019 doi

  32. [41]

    qspinlock: Introducing a 4-byte queue spinlock im- plementation.https://lwn.net/Articles/561775, July 31, 2013, 2013

    Waiman Long. qspinlock: Introducing a 4-byte queue spinlock im- plementation.https://lwn.net/Articles/561775, July 31, 2013, 2013. Accessed: 2018-09-19

    2013

  33. [42]

    Magnusson, A

    P. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. InProceedings of 8th International Parallel Processing Symposium, 1994.doi:10.1109/IPPS.1994.288305

    1994

  34. [43]

    Markatos and Thomas J

    Evangelos P. Markatos and Thomas J. LeBlanc. Multiprocessor syn- chronization primitives with priorities. In8th IEEE Workshop on Real-Time Operating Systems and Software. IEEE, 1991. doi:10.1016/ S1474-6670(17)51259-8

    1991

  35. [44]

    Xorshift rngs.Journal of Statistical Software, Articles,

    George Marsaglia. Xorshift rngs.Journal of Statistical Software, Articles,

  36. [45]

    Mellor-Crummey and Michael L

    John M. Mellor-Crummey and Michael L. Scott. Algorithms for scal- able synchronization on shared-memory multiprocessors.ACM Trans. Comput. Syst., 1991. URL:http://doi.acm.org/10.1145/103727.103729

    1991

  37. [46]

    Mellor-Crummey and Michael L

    John M. Mellor-Crummey and Michael L. Scott. Scalable reader-writer synchronization for shared-memory multiprocessors. InProceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP ’91. ACM, 1991. URL:http://doi.acm. org/10.1145/109...

    1991

  38. [47]

    Bug 13690 – pthread_mutex_unlock potentially cause invalid access.https://sourceware.org/bugzilla/show_bug.cgi? id=13690, February 14, 2012

    Atsushi Nemoto. Bug 13690 – pthread_mutex_unlock potentially cause invalid access.https://sourceware.org/bugzilla/show_bug.cgi? id=13690, February 14, 2012

    2012

  39. [48]

    Oyama, K

    Y. Oyama, K. Taura, and A. Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently. 1999

    1999

  40. [49]

    v008.i14

    URL:https://www.jstatsoft.org/v008/i14, doi:10.18637/jss. v008.i14

    doi

  41. [50]

    Tidex: A mutual exclusion lock

    Pedro Ramalhete and Andreia Correia. Tidex: A mutual exclusion lock. InProceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’16, 2016. URL:http: //doi.acm.org/10.1145/2851141.2851171

    2016

  42. [51]

    Reed and Rajendra K

    David P. Reed and Rajendra K. Kanodia. Synchronization with eventcounts and sequencers.Commun. ACM, 1979. URL:http: //doi.acm.org/10.1145/359060.359076

    1979

  43. [52]

    I. Rhee. Optimizing a FIFO, scalable spin lock using consistent memory. In17th IEEE Real-Time Systems Symposium, 1996. doi:10.1109/REAL. 1996.563705

    1996

  44. [53]

    Scott and Trevor Brown.Shared-Memory Synchronization, Second Edition

    Michael L. Scott and Trevor Brown.Shared-Memory Synchronization, Second Edition. Springer, 2024.doi:10.1007/978-3-031-38684-8

    2024 doi

  45. [54]

    Ticket lock - array of waiting nodes (awn),

    Pedro Ramalhete. Ticket lock - array of waiting nodes (awn),

  46. [55]

    R.K. Treiber. Technical Report RJ 5118, IBM Almaden Research Center, Systems programming: Coping with parallelism, 1986

    1986

  47. [56]

    Verner, A

    U. Verner, A. Mendelson, and A. Schuster. Extending Amdahl’s Law for Multicores with Turbo Boost.IEEE Computer Architecture Letters,

  48. [57]

    Be my guest: Mcs lock now welcomes guests.SIGPLAN PPoPP, 2016

    Tianzheng Wang, Milind Chabbi, and Hideaki Kimura. Be my guest: Mcs lock now welcomes guests.SIGPLAN PPoPP, 2016. doi:10.1145/ 3016078.2851160

    2016

  49. [58]

    Cocktail shaker sort, 2018

    Wikipedia. Cocktail shaker sort, 2018. URL:https://en.wikipedia.org/ wiki/Cocktail_shaker_sort

    2018

  50. [59]

    Gnome sort, 2018

    Wikipedia. Gnome sort, 2018. URL:https://en.wikipedia.org/wiki/ Gnome_sort

    2018

  51. [60]

    Stone and Dominique Thibaut

    Harold S. Stone and Dominique Thibaut. Footprints in the cache. SIGMETRICS Perform. Eval. Rev., 1986. doi:10.1145/317531.317533

    1986

  52. [61]

    un- defined behavior

    Liang Yuan, Chen Ding, Wesley Smith, Peter Denning, and Yunquan Zhang. A relational theory of locality.TACO – ACM Trans. Archit. Code Optim., 2019.doi:10.1145/3341109. 2025-09-05•Copyright Oracle and or its affiliates Dice and Kogan A Naming The nameReciprocating Locksarises f...

    2019 doi

  53. [67]

    Resource acquisition is initialization, 2022

    Wikipedia. Resource acquisition is initialization, 2022. URL:https: //en.wikipedia.org/wiki/Resource_acquisition_is_initialization

    2022

  54. [2003]

    URL:https://doi.org/10.1007/s00446-003-0088-6

    doi

  55. [2011]

    URL:http://arxiv.org/abs/1506.06796v2

    arXiv

  56. [2015]

    URL:http://concurrencyfreaks.blogspot.com/2015/01/ticket- lock-array-of-waiting-nodes-awn.html

    2015

  57. [2017]

    URL:https://doi.org/10.1109/LCA.2015.2512982

    2015

  58. [2021]

    URL:https://arxiv.org/abs/2110.05545,arXiv:2110.05545

    arXiv

  59. [2023]

    2025-09-05•Copyright Oracle and or its affiliates Reciprocating Locks

    URL:https://dspace.mit.edu/handle/1721.1/150219. 2025-09-05•Copyright Oracle and or its affiliates Reciprocating Locks

    2025

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.