pith. sign in

arxiv: 2606.24250 · v1 · pith:OWIE7ADWnew · submitted 2026-06-23 · 💻 cs.DC

Semantic Lock: Synchronization Based on the Analysis of the Operation Conflict Graph

Denis Korotchenko , Vitaly Aksenov This is my paper

Pith reviewed 2026-06-25 22:46 UTC · model grok-4.3

classification 💻 cs.DC
keywords SemanticLockoperation conflict graphsynchronization primitiveread-write lock generalizationconcurrent data structuresConcurrentHashMaprange queries
0
0 comments X

The pith

SemanticLock uses an operation conflict graph to allow concurrent execution of non-conflicting operations, generalizing the read-write lock.

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

The paper presents SemanticLock as a lock that analyzes conflicts between operations via a graph to decide which can safely run together. This model treats conflicts more flexibly than standard read-write locks, where writes block everything. Effectiveness is shown through a custom array with point and range queries plus an extension of ConcurrentHashMap that adds long-running operations. A sympathetic reader would care because finer-grained concurrency could reduce blocking in data structures with varied operation types.

Core claim

SemanticLock is a generalization of a read-write lock where conflicts exist between write operations and all other operations, based on the analysis of the operation conflict graph, and is effective in two demonstrated applications: a toy data structure supporting point queries and different range queries, and an augmentation of ConcurrentHashMap with additional long-running operations.

What carries the argument

The operation conflict graph, which models pairwise semantic conflicts between operations to grant concurrent access only to non-adjacent ones.

If this is right

  • In the array example, point queries can run concurrently with non-overlapping range queries.
  • ConcurrentHashMap gains support for long-running operations without blocking all other accesses.
  • Synchronization can become more selective, allowing pairs of operations to proceed if the graph shows no edge between them.
  • The same graph-based decision can be applied to other data structures that mix short and long operations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of new concurrent structures could define custom conflict relations upfront rather than using blanket read or write modes.
  • If graph maintenance proves cheap, the approach might reduce the need for coarse-grained locks in libraries that expose multiple operation kinds.
  • Runtime conflict detection could complement static analysis when adding operations to existing concurrent maps.

Load-bearing premise

That constructing and maintaining the operation conflict graph at runtime adds acceptable overhead while correctly identifying all conflicts that would make concurrent execution unsafe.

What would settle it

A performance measurement on the array or augmented ConcurrentHashMap showing that graph construction and maintenance time exceeds the throughput gain from extra concurrent operations.

read the original abstract

This paper presents a new lock, SemanticLock, based on the conflict graph between operations. We can consider it a generalization of a read-write lock where conflicts exist between write operations and all other operations. We demonstrate the effectiveness of our lock in two applications. In the first, we design a toy data structure: an array supporting point queries and different range queries. In the second, potentially of greater interest, we augment an existing concurrent data structure, ConcurrentHashMap, with additional long-running operations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript introduces SemanticLock, a synchronization primitive based on the analysis of an operation conflict graph. It generalizes the read-write lock by allowing conflicts to be defined between arbitrary operations (with writes conflicting with all others). Effectiveness is demonstrated via two applications: a toy array supporting point queries and multiple range queries, and an augmentation of ConcurrentHashMap to support additional long-running operations.

Significance. If the runtime construction of the conflict graph is shown to be complete and sound, the approach could enable higher degrees of concurrency than traditional locks in data structures whose operations have rich semantic relationships, particularly for long-running operations.

major comments (1)
  1. [SemanticLock definition and conflict-graph construction (throughout the core description)] The safety of SemanticLock rests on the claim that the operation conflict graph constructed at runtime contains every pair of semantically conflicting operations. The manuscript provides no general proof of completeness, no enumeration of conflicts for the demonstrated cases, and no argument that omitted edges cannot occur. This is load-bearing for both the toy array (point vs. range queries) and the ConcurrentHashMap augmentation (long-running ops), as an incomplete graph would permit unsafe concurrent execution.
minor comments (1)
  1. [Abstract] The abstract states the central claims but contains no equations, proofs, or performance numbers, making it impossible to assess support for the claims from the summary alone.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed feedback on SemanticLock. We address the major comment on conflict-graph completeness below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [SemanticLock definition and conflict-graph construction (throughout the core description)] The safety of SemanticLock rests on the claim that the operation conflict graph constructed at runtime contains every pair of semantically conflicting operations. The manuscript provides no general proof of completeness, no enumeration of conflicts for the demonstrated cases, and no argument that omitted edges cannot occur. This is load-bearing for both the toy array (point vs. range queries) and the ConcurrentHashMap augmentation (long-running ops), as an incomplete graph would permit unsafe concurrent execution.

    Authors: We agree that the current manuscript lacks an explicit general argument for completeness of the runtime conflict-graph construction and does not enumerate conflicts for the two applications. This is a substantive gap. In the revised manuscript we will add (1) a formal subsection defining semantic conflicts and arguing that the construction is complete by exhaustive pairwise checking of operation-type semantics at graph-build time, (2) an explicit enumeration of all conflicting pairs for the toy array (point query vs. each range query variant, with overlap conditions), and (3) the corresponding enumeration for the long-running operations added to ConcurrentHashMap, together with a short argument that no additional edges are possible because all operation pairs are considered. These additions will directly address the safety claim for the demonstrated cases. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation is self-contained without reduction to inputs

full rationale

The paper introduces SemanticLock as a generalization of read-write locks via operation conflict graph analysis and demonstrates it on two applications (toy array with point/range queries; augmented ConcurrentHashMap). No equations, fitted parameters, or self-citation chains appear in the provided text. The central construction (building/maintaining the conflict graph at runtime) is presented as a design choice rather than derived from prior results by the same authors. No step reduces by definition or construction to its own inputs, satisfying the criteria for a non-circular finding.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be identified from the given information.

pith-pipeline@v0.9.1-grok · 5602 in / 930 out tokens · 17999 ms · 2026-06-25T22:46:43.575729+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 14 canonical work pages

  1. [1]

    Parallel Combining: Benefits of Explicit Synchronization

    1 Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. Parallel Combining: Benefits of Explicit Synchronization. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Fer- reira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 11:...

    2018

  2. [2]

    URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.11, doi:10.4230/LIPIcs.OPODIS.2018.11

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.11, doi:10.4230/LIPIcs.OPODIS.2018.11. 2 B. R. Badrinath and Krithi Ramamritham. Semantics-based concurrency control: Beyond commutativity. ACM Trans. Database Syst. , 17(1):163–199,

    work page doi:10.4230/lipics.opodis.2018.11 2018

  3. [3]

    doi:10.1145/128765. 128771. 3 Guy E. Blelloch and Yuanhao Wei. Verlib: Concurrent versioned pointers. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Pro- gramming, PPoPP ’24, page 200214, New York, NY, USA,

    work page doi:10.1145/128765

  4. [4]

    doi:10.1145/3627535.3638501

    Association for Computing Machinery. doi:10.1145/3627535.3638501. 4 Trevor Brown, Aleksandar Prokopec, and Dan Alistarh. Non-blocking interpolation search trees with doubly-logarithmic running time. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’20, page 276291, New York, NY, USA,

    work page doi:10.1145/3627535.3638501

  5. [5]

    doi:10.1145/3332466

    Association for Computing Machinery. doi:10.1145/3332466. 3374542. 5 P. J. Courtois, F. Heymans, and D. L. Parnas. Concurrent control with readers and writers. Commun. ACM , 14(10):667668, October

    work page doi:10.1145/3332466

  6. [6]

    doi:10.1145/362759.362813. D. Korotchenko, V. Aksenov XX:7 6 Dave Dice, Yossi Lev, and Mark Moir. Scalable statistics counters. In 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’13 , pages 43–52. ACM,

    work page doi:10.1145/362759.362813

  7. [7]

    7 Vincent Gramoli

    doi: 10.1145/2486159.2486182. 7 Vincent Gramoli. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP 2015, page 110, New York, NY, USA,

    work page doi:10.1145/2486159.2486182 2015

  8. [8]

    doi:10.1145/2688500.2688501

    Association for Computing Machinery. doi:10.1145/2688500.2688501. 8 Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Flat combining and the synchronization-parallelism tradeoff. pages 355–364, 06

    work page doi:10.1145/2688500.2688501

  9. [9]

    doi:10.1145/1810479. 1810540. 9 Maurice Herlihy and Eric Koskinen. Transactional boosting: a methodology for highly- concurrent transactional objects. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , PPoPP ’08, page 207216, New York, NY, USA,

    work page doi:10.1145/1810479

  10. [10]

    In: Chatterjee, S., Scott, M.L

    Association for Computing Machinery. doi:10.1145/1345206.1345237. 10 Maurice P. Herlihy and Jeannette M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. , 12(3):463492, July

    work page doi:10.1145/1345206.1345237

  11. [11]

    1145/78969.78972

    doi:10. 1145/78969.78972. 11 Yuh-Jzer Joung. Asynchronous group mutual exclusion (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing , PODC ’98, page 5160, New York, NY, USA,

    arXiv

  12. [12]

    doi: 10.1145/277697.277706

    Association for Computing Machinery. doi: 10.1145/277697.277706. 12 Nikita Koval, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan Alistarh. Lincheck: A practical framework for testing concurrent data structures on jvm. In Con- stantin Enea and Akash Lal, editors, Computer Aided Verification , pages 156–169, Cham,

    work page doi:10.1145/277697.277706

  13. [13]

    doi:10.1007/978-3-031-37706-8_8

    Springer Nature Switzerland. doi:10.1007/978-3-031-37706-8_8 . 13 David B. Lomet. Key range locking strategies for improved concurrency. In Proceedings of the 19th International Conference on Very Large Data Bases , VLDB ’93, page 655664, San Francisco, CA, USA,

    work page doi:10.1007/978-3-031-37706-8_8

  14. [14]

    15 Aleksandr Potapov, Maksim Zuev, Evgenii Moiseenko, and Nikita Koval

    doi:10.1109/ICPP.2013.39. 15 Aleksandr Potapov, Maksim Zuev, Evgenii Moiseenko, and Nikita Koval. Testing concurrent algorithms on jvm with lincheck and intellij idea. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis , ISSTA 2024, page 18211825, New York, NY, USA,

    work page doi:10.1109/icpp.2013.39 2013

  15. [15]

    doi:10.1145/3650212

    Association for Computing Machinery. doi:10.1145/3650212. 3685301. 16 Matthew Rodriguez, Vitaly Aksenov, and Michael Spear. Skip hash: A fast ordered map via software transactional memory. In 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS) , pages 956–966. IEEE,

    work page doi:10.1145/3650212 2025

  16. [16]

    doi:10.1109/ICDCS63083.2025. 00097. 17 Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing , pages 204–213,

    work page doi:10.1109/icdcs63083.2025 2025