# CALock: Multi-granularity locking in dynamic hierarchies

Ayush Pandey, Julien Sopena, Marc Shapiro, Swan Dubois

► To cite this version:

Ayush Pandey, Julien Sopena, Marc Shapiro, Swan Dubois. CALock: Multi-granularity locking in dynamic hierarchies. IPDPS 2025 - 39th IEEE International Parallel and Distributed Processing Symposium, Jun 2025, Milan, Italy. hal-04989563

HAL Id: hal-04989563

https://hal.sorbonne-universite.fr/hal-04989563v1

Submitted on 21 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# CALock: Multi-granularity locking in dynamic hierarchies

Ayush Pandey

Julien Sopena

Marc Shapiro

Swan Dubois

Sorbonne-Université, LIP6

Sorbonne-Université, LIP6

Sorbonne-Université, LIP6 & INRIA

Sorbonne-Université, LIP6

Paris, France

Paris, France

Paris, France

Paris, France

ayush.pandey@lip6.fr

julien.sopena@lip6.fr

marc.shapiro@acm.org

swan.dubois@lip6.fr

**Abstract**—Hierarchies are fundamental structures across various disciplines, modelling hierarchical relationships in computer science, biology, social networks, and logistics. However, dynamic and concurrent updates in real-world systems necessitate synchronisation techniques for maintaining data consistency despite concurrent access. This paper explores a novel approach called CALock to synchronise operations on hierarchies by utilising a labelling scheme that facilitates multi-granularity locking. Our approach addresses both concurrent data reads and writes as well as structural modifications. CALock exploits the hierarchical topology via a new labelling scheme to identify the common ancestors of vertices. This enables a thread to identify an appropriate lock granule for its lock request. Leveraging variable lock granularity optimises operations across the hierarchy while ensuring consistency and performance. We provide a detailed discussion of the CALock labelling and the locking algorithm, prove its properties, and evaluate it experimentally. CALock remains competitive with previous labelling schemes on static hierarchies and has better concurrency and throughput when structural modifications change the hierarchy. In particular, CALock improves throughput by up to 4.5 times and lock response time by up to 1.5 times for workloads that contain structural modifications.

**Index Terms**—Hierarchical data, Graphs, Locking, Synchronization, Guarding ancestors.

## I. INTRODUCTION

A hierarchy is a rooted graph (usually acyclic) that applications navigate from the defined root vertex, most often downwards. In a hierarchy, the vertex at any level 'contains' all reachable vertices below its level. A simple example is a relational database. A database is composed of a collection of *tablespaces*. A tablespace contains several *datafiles* that contain *tables*. A table is a collection of *rows* where the data is actually stored [1]. With recent developments in graph databases, hierarchies are widely used by social media applications via the RDF model [2].

An application often needs to access and modify the data and the relationships between them concurrently. This modification can occur in a structured database [3] via predicate queries [4]. Due to the underlying representation, locking is the predominant technique to ensure data consistency and integrity in this context.

Locking methods for hierarchies generally associate a lock with a vertex in the hierarchy, which we call its *guard*. Before accessing a vertex, its guard must be locked; to access an edge requires locking both its source and destination vertices.

A vertex that a transaction requests access to is called the *lock target*, i.e. to lock a target, a transaction must lock the guard of that target. The set of targets protected by a guard is the *lock grain* [5]. The lock grain is the smallest set of vertices that need to be locked to ensure that the lock targets are accessed atomically. A grain is guarded by a guard vertex, the root of a subgraph containing the lock targets. For efficiency, it may be opportune to *coarsen* the guard for the targets, such that to lock multiple lock targets, a lock on a single guard is sufficient due to the containment property between the vertices of a hierarchy.

*Multi-granularity locking* (MGL) [6] techniques exploit the topology of the graph to identify a pertinent guard for a given target. Since grain size (the *granularity*) depends on the topology of the graph and the lock request, different lock requests have different granularity, hence the name.

The choice of granularity is a performance trade-off. Coarse-grain locking restricts concurrency; in the limit, if the grain is the whole graph, all transactions execute sequentially. Fine-grain locking (e.g., if every target is its own guard) maximises concurrency, but accessing a large subgraph suffers the high cost of acquiring many locks. In practice, locking approaches need to balance maintaining data consistency against concurrency and the cost of locking based on the workload. The absence of a theoretically optimal locking configuration makes MGL techniques attractive.

Although there already exist practical MGL algorithms for graphs that do not undergo structural modifications, this is not the case for graphs whose structure can mutate, as we show in Section II. A structural modification operation adds or removes vertices and/or edges and may conflict with ordinary operations or another structural modification. Such operations affect the identification of lock granules as their size and shape now depend on the new topology.

*Context:* This work on locking focuses on a multi-core system where threads concurrently access a shared graph. Such use cases, prevalent as graph processing applications, allow using a single centralised scheduler that decides the ordering of the lock requests. Locking can still be useful in distributed deployments like HPC clusters where communication can be guaranteed to be quasi-instantaneous. Geo-distributed graphs and synchronisation are out of the scope of this work. Locking in any form is inefficient for use cases where the graph
is geo-distributed, and the communication latency (ergo, the
synchronisation delay) is high.

The requirement for any locking technique over graphs is to
protect the vertices and edges of the graph against concurrent
write access. Writes can modify the data on the vertices or
add/remove edges from the graph. An application that uses
CALock can have multiple threads that concurrently access the
graph. Each thread can request a lock on a set of vertices.lock
targets). The locking algorithm then grants the lock request
by locking a single vertex(the guard) that protects the set of
vertices. Once a thread identifies a guard and issues a lock
request, the guard cannot be changed, i.e. the guard is fixed
for the duration of the lock. This is to ensure that the lock grain
remains consistent for the duration of the lock. If a conflict
is detected between two lock requests, one of the threads is
blocked until it is notified to resume, i.e., there is no busy
waiting. In our design, we assume that the threads are not
malicious and do not try to circumvent the locking and conflict
detection mechanism.

Contribution: Existing MGL techniques like intention
locks [6] use the topology of the hierarchy to detect lock
conflicts but require multiple traversals from the root of the
graph to the vertices being locked. This makes them expensive
for non-tree-like hierarchies, for example, DAGs. Label-based
techniques [7]–[9] use an ordering of vertices to assign labels
that eliminate the need for traversals. However, these have
poor performance over dynamic graphs due to the overhead
of relabelling.

We propose a new labelling scheme based on path proper-
ties that supports multi-granularity locking. *Common-Ancestor
lock (CALock)* is based on a labelling that efficiently computes
the closest common ancestor of a set of vertices in a rooted
directed graph. By choosing the closest common ancestor of
a set of lock targets as their guard, CALock minimises grain
size. By avoiding a fixed ordering of vertices when using paths,
CALock circumvents expensive relabelling while providing
the same locking guarantees as other MGL techniques. The
label of a vertex in the graph is a set of its common ancestors,
computed recursively via breadth-first traversal (see Section
III).

This paper makes the following contributions:

1) Definition and proof of correctness of CALock labelling.

2) Algorithms for labelling and conflict detection.

3) Evaluation of CALock under STMBench7 [10] com-
pared to the state of the art. <fnref n="1" />

Section II presents an overview of previous multi-
granularity locking approaches. Section III presents the for-
mal definition and correctness proof of CALock’s labelling
scheme. Section IV presents the details of the labelling using
examples. Section V provides details on the implementation of
CALock. Section VI discusses the properties of the CALock
locking algorithm. Section VIII presents the evaluation of
CALock using STMBench7.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Intention exclusive locks on paths to lock H and J in exclusive mode.</figcaption></figure>

II. STATE OF THE ART

Several MGL techniques are used in practice. Classical
path-based techniques like intention locks forego additional
metadata and utilise traversals to lock the hierarchy. Label-
based techniques use a partial ordering of vertices to deduce
ancestor-descendent relationships. This ordering is often stored
as additional metadata. In this section, we discuss the most
popular and recent MGL techniques and compare CALock
against them via benchmarks in Section VIII.

A. Intention lock

Intention lock [6] is an MGL technique in which the vertices
along the paths of the graph leading to the lock targets are
marked with intention locks. These locks “tag” the vertices,
indicating that an actual lock (shared or exclusive) is being
acquired at a finer granularity along this path. Other threads
use intention tags to check for conflicts early. While placing
tags along a path, if a thread encounters a tagged vertex in
conflicting mode, it waits until the tag is cleared or not in
conflict anymore. Figure 1 shows an example of intention
exclusive locks on a graph. In order to lock H and J in
exclusive mode, a thread acquires intention exclusive (IX)
locks on the paths to H and J. This requires depth-first
traversing the graph from the root to H and J.

Commercial databases like SQLServer [11] use intention
locks to optimise synchronised access to data and indices.
Intention locks may have a high latency for a lock request
because of the traversals required to place intention tags
along the paths. These traversals are especially expensive for
graphs with many edges. Intention locks are thus unsuitable
for dynamic graphs where the topology changes frequently.
In practice, like in SQLServer, they are only used when the
underlying hierarchy is a tree.

B. DomLock

DomLock [7] is an MGL technique suitable for rooted
directed graphs. It labels each vertex with an integer *interval*
of the form [*min*, *max*], assigned via a post-order graph
traversal. Figure 2 shows an example of such labelling. A

<footnote n="1">¹An open source artifact which implements CALock and other contem-
porary MGL techniques can be found at https://anonymous.4open.science/r/
CALockBench-B117/</footnote>
leaf has a unit interval, e.g. vertex E has the label [2, 2]. The interval for an internal vertex is the minimum of the *min* values and the maximum of the *max* values from the intervals of its children. For example, vertex C has two children, F and G; its interval is [3, 4]. Hence, we say that C subsumes the intervals of the vertices F and G.

<figure><img src="image_3.png" /><figcaption>DomLock on G: [3, 4] with grain: {F, G, H, I J}</figcaption></figure>

<caption>Fig. 2: DomLock intervals (top), MID intervals (middle) and FlexiGran levels (bottom).</caption>

Based on the traversal order, a vertex can sometimes guard its siblings. For example, vertex F is not a descendant of vertex G, but the interval of G still subsumes the interval of F. This is called a *false subsumption*.

With DomLock, the lock guard for a set of lock targets is the deepest vertex with the smallest interval that subsumes the intervals of the lock targets. For example, in Figure 2, to lock H and J, the grain has the interval [3, 4]. G is the deepest vertex that subsumes [3, 4], so a lock is requested on G.

When a structural modification is performed, these intervals need to be recomputed. Since the intervals are assigned via a post-order traversal, complete relabelling is often necessary since the intervals are not elastic. This is expensive because inserting one leaf vertex between two existing vertices causes the interval of the root to change. Hence, the grain is the entire graph for structural modifications, blocking all other operations. For example, in Figure 2, if a vertex K is inserted between H and I, K's interval would be [4, 4]. Consequently, the intervals of I and J would change to [5, 5]. When this is propagated to the root, the interval of A will change to [1, 5].

DomLock is especially expensive because false subsumptions restrict concurrency. For example, in Figure 2, a lock on G prevents another thread from locking F even though they are siblings and do not lie on the same path from the root. Furthermore, when the graph changes, the cost of updating the intervals is high because a DFS traversal over the entire graph is performed.

### C. Multi-Interval DomLock

Multi-Interval DomLock (MID) [8] addresses the problem of false subsumptions by maintaining multiple integer intervals

on a vertex. DomLock assigns an interval to a vertex based on a post-order traversal over the graph. In addition, MID performs a pre-order traversal called “DFS-on-image.” These two traversals compute two intervals per vertex, as shown in Figure 2. Two grains overlap iff both their intervals overlap (the DomLock-based and the DFS-on-image-based intervals). However, this does not entirely eliminate false subsumptions. For example, in figure 2, the DFS intervals and the DFS on image intervals of G and F overlap even though F is not a child of G. This is a false subsumption. Moreover, maintaining two intervals per vertex aggravates the problem of relabelling when the graph topology is modified, as at least two DFS passes are required for relabelling, incurring twice the cost.

### D. FlexiGran

Flexible Granularity locking (Flexigran) [12] aims to provide a mechanism for fine-grain and MGL locks to co-exist efficiently. In addition to the DomLock intervals, it uses the level of each vertex in the hierarchy. The level of a vertex is the length of the shortest-longest path from the root of the hierarchy to said vertex. If two vertices have the same interval, for example, F and H in Figure 2, their level (in red) is used to identify the ancestor-descendant relationship. In this case, F is the ancestor of H.

MGL Lock is implemented via DomLock and Fine-grain lock in flexigran is a read/write lock on a single vertex. When checking if two MGL locks are compatible, the intervals of their guards are tested for overlap. Disjoint intervals indicate that the two locks are MGL compatible. When an overlap is detected, the levels are checked to ensure that the overlap is topological and not a false positive due to the order in which intervals are assigned. When checking two fine-grain locks for conflict, the lock guards for the lock requests are compared. If two fine-grain lock requests are on the same vertex, they conflict if at least one of the requests is for a write lock. To test the compatibility of an MGL lock with a fine-grain lock, it is necessary to perform a reachability check between the guards of the MGL lock and the fine-grain lock. To do so, a search is initiated from the guard of the MGL lock, and if the fine-grain lock guard is reachable from the MGL lock guard, then the two locks are incompatible since they lie in the same MGL grain.

Figure 2 shows the intervals and levels of the vertices in the hierarchy used for FlexiGran. Flexigran can reduce false subsumption by comparing levels when intervals overlap. If two vertices have the same level, they are considered siblings when their intervals overlap. For example, in Figure 2, the intervals of F and G overlap, but their level is the same, so they are considered siblings.

## III. FORMAL FUNDAMENTALS

In this section, we present the formal definitions of the concepts used in CALock. The casual reader may skip this section.

Let $G = (V, E)$ be a directed graph. $V$ is its set of vertices, connected by directed edges in the set $E \subseteq V \times V$. A rooted
graph has a distinguished vertex $r \in V$ such that all other vertices are reachable from $r$.

A pair of vertices $(u, v)$ can be connected by a sequence of edges, called the path between $u$ and $v$, noted $p$. The set of vertices of $p$ is noted $\mathcal{V}(p)$. The length $l_p$ of this path is the size of $\mathcal{V}(p)$ i.e. $l_p = |\mathcal{V}(p)|$.

In the general case, several such paths may exist between a pair of vertices. The set of paths between $u$ and $v$ is noted $\mathcal{P}_{(u,v)}$. The depth $\delta(v)$ of a vertex $v$ is the length of the shortest path in the set $\mathcal{P}_{(r,v)}$.

**Definition 1 (Ancestor and Descendent).** An ancestor of a vertex $u$ is a vertex $v$ in $G$ that lies on a path from $r$ to $u$. The vertex $u$ is then called the descendant of vertex $v$.

**Definition 2 (Guarding Ancestor).** A guarding ancestor of a vertex $u$ is a vertex $v \in G$ that lies on all paths from $r$ to $u$. The set of guarding ancestors of $u$ is noted $L_u$.

**Definition 3 (Lowest guarding Ancestor).** The lowest guarding ancestor $LGA(u)$ of a vertex $u$ is a guarding ancestor of $u$ with the maximum depth.

**Definition 4 (Common Ancestor).** A common ancestor (CA) of two vertices $u$ and $v$ is a vertex $c$ that is an ancestor of both $u$ and $v$.

**Definition 5 (Lowest Common Ancestor).** The lowest common ancestor $LCA(u, v)$ of two vertices $u$ and $v$ is a common ancestor of $u$ and $v$ with the maximum depth.

### A. Lowest Guarding Common Ancestor

The Lowest Guarding Common Ancestor $LGCA(Q)$ of a set of vertices $Q$ is the deepest vertex that is both a guarding ancestor and a common ancestor of all vertices in $Q$. Fischer et al. [13] derive the following relationships between the LGA and the LGCA of vertices in a rooted DAG.

**Lemma 1.** $LGCA_G(v) = LGCA_G(parents_G(v))$

**Definition 6.**

$$LGCA_G(w_1, ..., w_k) = LGCA_G(w_1, LGCA_G(w_2, ..., w_k))$$

The $LGCA$ of a set of vertices is the intersection of the sets of guarding ancestors of those vertices. We have the following theorem:

**Theorem 1.**

$LGCA_G(v, w)$ is the vertex of the maximum depth in $L_v \cap L_w$

*Proof.* Let $l = LGCA_G(v, w)$ be the LGCA of $\{v, w\}$; we need to show that $l$ is the deepest vertex in $L_v \cap L_w$.

Let's assume that a vertex $l' \neq l$ lies on all paths from $l$ to $v$ and $l$ to $w$ in $G$. Since $l'$ lies on the paths in the sets $\mathcal{P}_{(l,v)}$ and $\mathcal{P}_{(l,w)}$, inductively, $l'$ also lies on all the paths from the root ($r$) of the graph to the vertices $v$ and $w$. If $l'$ lies on these paths, then it is a guarding ancestor of $v$ and $w$, and the following holds: $(l' \in L_v) \wedge (l' \in L_w) \equiv l' \in L_v \cap L_w$.

Since $l'$ lies on the paths to $v$ and $w$ after $l$, by the definition of depth $\delta(v)$ of a vertex, $\delta(l') > \delta(l)$.

Now we have two conclusions, $l' \in L_v \cap L_w$ and $\delta(l') > \delta(l)$.

Since $l'$ is deeper than $l$, it should be the deepest member of $L_v \cap L_w$. This means that $l'$ is the LGCA of $v$ and $w$. But this contradicts our original assumption that $l$ is the LGCA of $v$ and $w$. This means our assumptions on $l'$ contradict the definition $l = LGCA_G(v, w)$ and $l$ is the deepest element in the set $L_v \cap L_w$. □

## IV. CALOCK LABELLING SCHEME

The CALock label for a vertex is the set of its guarding ancestors. To ease the implementation, we derive a recursive function from the definitions in Section III that can be used to compute these labels. An implementation of this function is shown in Algorithm 1.

### A. Recursive labelling function

Theorem 1 is defined for rooted DAGs. We combine it with the definitions and lemmas from Section III-A to derive a recursive function that we use to label the vertices in a graph. To this end, Lemma 1 can be rewritten using Definition 6 as follows:

$$LGCA_G(v) = LGCA_G(p_1, LGCA_G(p_2, ..., p_k)) \qquad (1)$$
where $p_1, p_2, ..., p_k$ are the parents of $v$

On combining equations 1 and theorem 1; $LGCA_G(v)$ is the deepest vertex in $L_{p_1} \cap L_{p_2} \cap ... \cap L_{p_k}$ where $p_1, p_2, ..., p_k$ are the parents of $v$.

Therefore, the sets of guarding ancestors of parents of $v$ are enough to compute the lowest guarding ancestor of $v$. We use this property to recursively compute the labels of the vertices in a graph using the following function.

$$L_v = \begin{cases} \{v\} & v \text{ is the root} \\ \{v\} \cup \{\cap_{u \in parents(v)} L_u\} & \text{otherwise} \end{cases} \qquad (2)$$

<figure><img src="image_4.png" /><figcaption>Lock on G: {A,C,G} with grain: {I, J}</figcaption></figure>

<caption>Fig. 3: CALock labels</caption>
## B. Labelling graphs recursively

1) Labelling acyclic graphs: Labelling starts at the root of the graph when the function AssignLabel(r) is called. It uses Relation 2 implemented in lines 15 - 21 to assign the labels. The root vertex does not have parents, so the label of the root is the set containing the ID of the root itself (lines 10 - 14). For example, in figure 3 vertex A has the label {A}.

Then, the children of the vertex v are explored via a breadth-first traversal over the graph. Using the labels of the parents, the label of the child is computed via Relation 2. For example, in figure 3, the label of vertex B is {A, B} since it has only one parent. Vertex H has two parents which have the labels {A, C, F} and {A, C, G} respectively. Their set intersection is {A, C}. Using Relation 2, the label of H is {A, C, H}. The graph is explored and labelled until the recursion reaches a fix-point and terminates (line 18).

2) Labelling strongly connected components: Theorem 1 assumes that the graph does not contain strongly connected components. In real-life applications, maintaining this constraint is difficult. There are strategies to find strongly connected components in a directed graph [14]–[16] that can be contracted by vertex contraction [17]. We, however, maintain that finding and eliminating strongly connected components is not required to identify lock grains using CALock when the labels are assigned using Relation 2.

Assume that $N \subseteq V$ is a set of vertices of a graph that are strongly connected. Since every vertex in $N$ is reachable from every other vertex in $N$, the path set $P_{(u,v)}$ for any pair of vertices $u, v \in N$ contains the same vertices in different orders. Hence, every vertex has the same set of guarding ancestors. The function BFLabel recurses over vertices in $N$ until all the paths to a vertex are explored, and its label no longer changes (line 18). When BFLabel terminates, all vertices in $N$ have the same label.

Therefore, Relation 2 is sufficient to label rooted directed graphs with strongly connected components. An implementation of recursive labelling is shown in Algorithm 1.

3) Relabelling graphs: The topology of a graph can change due to structural modifications. Then, the labels of the vertices need to be recomputed. The same function AssignLabel(v) can be used to relabel the graph. Relabelling begins at a vertex affected by the structural modification via the function AssignLabel(v). In the same fashion as the initial labelling, the parents of the affected vertex are used to compute its label and then recursively of its descendants. Relabelling is terminated as soon as it reaches a fix-point (line 18).

## V. MULTI-GRANULARITY LOCKING WITH CALOCK

In CALock, when a thread wants to lock a set of lock targets, it issues a lock request for the LGCA of targets, computed by taking a set intersection of their labels (see theorem 1). This LGCA is a vertex in the graph and is the guard for this lock request. A guard is the root of the smallest grain that contains the lock targets. For example, in Figure 3,

<caption>**Algorithm 1** Labelling the graph</caption>

1: **procedure** ASSIGNLABELS(v)
2:     **queue**.PUSH(v)
3:     **while** queue.HASNEXT() **do**
4:         v ← queue.NEXT()
5:         BFLABELA(v, queue)
6:     **end while**
7: **end procedure**
8: **procedure** BFLABELA(v, queue)
9:     C ← CHILDREN(v)
10:    **if** parents(v) = ∅ **then**
11:        v.label ← {v}
12:        queue.PUSH(C)
13:    **return**
14: **end if**
15:    P ← PARENTS(v)
16:    tempLabel ← INTERSECTION(P.labels)
17:    tempLabel APPEND(v)
18:    **if** v.label ≠ tempLabel **then**
19:        v.label ← tempLabel
20:        queue.PUSH(C)
21:    **end if**
22: **end procedure**

to lock I and J, we find their LGCA, which is G and place a lock on G (the lock guard).

When the thread identifies the LGCA, it issues a lock request by adding its request to a pool used to identify conflicts (Section V-A). The thread then proceeds to check for conflicts and blocks if one exists. In the absence of conflicts, the thread proceeds to its critical section.

### A. Identifying lock conflicts

In MGL on graphs, conflict detection is not as simple as testing for read/write conflicts. Since lock guards have a grain they protect, it is necessary to ensure that the grain remains exclusive for a writer. With CALock, two conditions indicate a lock conflict. If both conditions hold for a pair of lock requests, they conflict.

* The lock requests have a *mode conflict*, i.e. a read/write conflict.

* The lock requests have a *grain overlap* i.e. they are trying to lock overlapping grains.

To remain fair and prevent thread starvation, CALock uses sequence numbers to resolve conflicts. The sequence numbers indicate the order in which the locks are requested. In the presence of conflicts, threads are granted locks in a *First come, first served* order.

A thread that wants to lock a set of targets creates a lock request and adds it to a *lock pool* for conflict detection. The request contains the following data.

* **Thread ID:** of the thread requesting the lock

* **Guard ID:** of the vertex being locked to lock the set of targets.

* **Guard label:** Label of the lock guard vertex

* **Sequence number:** allocated to the lock request when added to the lock pool.

* **Activity Indicator:** used by other threads to wait in the presence of conflicts.

* **Lock mode:** read or write
The lock pool is an array containing one entry per thread. Initially, and when the thread is not holding a lock, its entry is `NULL`. Algorithm 2 shows the flow of lock acquisition and conflict detection in the lock pool. When a thread arrives in the lock pool with the information of the lock it wants to acquire, it is given a sequence number (line 6) and it sets its activity indicator to true (line 7) indicating that it is active and using the lock. With this additional information, the lock request is added to the pool (line 8). To conserve the first come, first served order and prevent race conditions where a later lock request is granted first before the thread with an earlier request could detect the conflict, the three steps involving the assignment of a sequence number, setting the activity indicator and addition to the lock pool are done atomically.

After the lock request is added to the pool, the thread checks for conflicts with other requests in the pool.

* **Mode conflict:** is checked by comparing the lock modes in the requests.

* **Grain overlap:** is checked using the guard ID and guard label of the requests. For two lock requests $R_1$ and $R_2$, if the guard ID of $R_1$ is present in the guard label of $R_2$ or vice-versa, then the grains overlap.

* **Arrival order:** If there is a mode and grain conflict, the request with a lower sequence number is granted first.

A thread checks these conditions (line 11) by iterating over the pool (line 10). When requesting a lock, any thread $T$ can be blocked for a maximum of $n$ turns where $n$ is the maximum number of threads. After $n$ blocks, the sequence number of $T$ will be the lowest among all requests in the lock pool, and it will be allowed to proceed. This is essential to prevent thread starvation.

Figure 4 shows the snapshot of a lock pool in use by threads. This pool contains three active threads $T_1, T_2$ and $T_7$. $T_7$ arrives first and is assigned the sequence number 1. $T_1$ and $T_2$ arrive later and have sequence numbers 2 and 3, respectively. $T_1$ and $T_2$ conflict because they have overlapping grains. $T_2$ requests a lock on C that overlaps with the grain locked by $T_1$. This is detected by checking if C is present in the label of G, i.e. $C \in \{A, C, G\}$. To resolve the conflict, $T_1$ is granted a lock since it arrived first, and $T_2$ has to wait for $T_1$ to release the lock. $T_7$ does not have a conflict with any thread and acquires a lock on B.

## B. Structural modifications, locking and relabelling

CALock can be utilised for static graphs whose structure does not change and for dynamic graphs that change at runtime. Here, we explain the locking and relabelling mechanism for dynamic graphs.

**Vertex addition and deletion:** Adding a vertex to the graph does not change the observable topology because this new vertex is not connected to the graph, and hence, it is also not reachable from the root. So, addition does not require locking or relabelling of any kind. Deleting a vertex that does not have any edges does not require synchronisation either because a disconnected vertex is not reachable from the root of the graph.

<caption>**Algorithm 2 Lock acquisition request in the lock pool**</caption>

1: $GSeq$: Global sequence number for lock requests
2: $Mutex$: Mutex used when adding requests to the lock pool
3: **Condition**: Atomic boolean value used by waiting threads when in conflict
4: **procedure** LOCK(req, threadID)
5:     LOCK(Mutex)
6:     req.Seq $\leftarrow$ Gseq + $
$7:     req condition.TESTANDSET(true)
8:     Pool[threadId] $\leftarrow$ req
9:     UNLOCK(Mutex)
10:    **for** all lock $\in$ Pool $\setminus$ threadID **do**
11:        **if** lock $\neq$ NULL $\land$ (req.HASRWCONFLICT.lock))
12:            $\land$ (lock.guardID $\in$ req.label $\lor$ req.guardID $\in$ lock.label)
13:            $\land$ (req.Seq > lock.Seq) **then**
14:                thread.WAIT.locker condition)
15:            **end if**
16:        **end for**
17:    **return** true
18: **end procedure**
17: **procedure** UNLOCK.lock)
18:    lockPool REMOVE.lock)
19:    lock condition CLEAR()
20:    lock condition NOTIFY_ALL()
21: **end procedure**

However, a lock is required to delete a vertex that is reachable from the root, i.e., connected to the graph. To do this, a write (exclusive) lock is taken on the LGCA of the vertex that needs to be deleted. The LGCA guards all the paths reaching this vertex and prevents inconsistent access. Once the lock is acquired, the vertex is disconnected from the graph and deleted. After a vertex is deleted, relabelling might be necessary if the deleted vertex's descendants are still connected to the graph since the set of their ancestors has changed. Relabelling is done by recursively calling the function `BFLabel()` in Algorithm 1 on the children of the deleted vertex. The lock acquired to delete the vertex is released after the relabelling.

**Edge addition and deletion:** Adding and deleting edges to the graph changes its topology and the paths to the vertices. Both operations are performed under a write (exclusive) lock. When adding or deleting an edge between a source vertex $u$ and a target vertex $v$, a write (exclusive) lock is taken on the LGCA of $u$ and $v$. Both operations change the paths to a vertex, so relabelling is initiated at the target ($v$) of the affected edge via `BFLabel()` function in Algorithm 1.

When a vertex has only one incoming edge, deleting that edge disconnects it from the graph. In this case, relabelling can be omitted because the target vertex $v$ has no parents and is also not reachable from the root of the graph.

**Relabelling a sub-graph:** When a structural modification occurs, the grain in which the modification takes place needs to be relabelled. Unlike DomLock, MID and FlexiGran, in which the relabelling happens under a global mutex, relabelling in CALock is done under the same lock acquired to perform the structural modification. Relabelling begins at the vertex affected by the modification and recursively relabels its descendants.
<table><caption>Fig. 4: Lock pool containing details of locks held by threads</caption><thead><tr><th>T<sub>1</sub></th><th>T<sub>2</sub></th><th>T<sub>3</sub></th><th>T<sub>4</sub></th><th>T<sub>5</sub></th><th>T<sub>6</sub></th><th>T<sub>7</sub></th></tr></thead><tbody><tr><td>G, read, 2, {A, C, G}</td><td>C, write, 3, {A, C}</td><td>NULL</td><td>NULL</td><td>NULL</td><td>NULL</td><td>B, read, 1, {A, B}</td></tr></tbody></table>

## VI. PROPERTIES OF CALOCK

The properties of any algorithm are important in guaranteeing behavioural stability. This section shows that CALock is safe, live and fair. However, it's crucial to emphasise that the discussion of these formal properties only holds true value when the implementation of the locking algorithm is correct. CALock requires the assignment of lock request sequence numbers, setting the activity indicator and addition of the lock pool to happen atomically. In our implementation, we use a mutex to achieve this.

### A. Safety

A thread holding a write lock on a guard has exclusive access to the corresponding grain. When a thread requests a write lock, the lock is granted only if no other thread can access this grain.

**Discussion:** By contradiction, assume that two threads $T_1$ and $T_2$ are granted a write lock on the same vertex $v$. Then, the lock pool would contain, at indices 1 and 2 respectively, two lock requests $R_1$ and $R_2$ with the same lock target $v$ and lock mode $wl$. However, they would have different sequence numbers since they are assigned atomically before the requests are added. At the entry to the critical section, $T_1$ (resp. $T_2$) iterates over the pool to check for conflicts of three kinds (Mode conflict, grain conflict, sequence number conflict). Since the iteration is always done in the same order, $T_1$ would detect a mode and grain conflict with $T_2$ and block if its sequence number is higher and vice-versa. Hence, $T_1$ and $T_2$ are never simultaneously granted a lock on $v$. Therefore, CALock is safe.

### B. Liveness

When a thread requests a lock, the lock is guaranteed to be granted eventually, i.e., The lock acquisition algorithm does not block forever.

**Discussion:** In a correct implementation of an application that uses CALock, when a thread leaves its critical section, it releases the lock it holds, and this is guaranteed to happen, i.e. threads do not sleep after lock acquisition. The lock pool prevents a thread from holding multiple locks. If a thread wishes to lock multiple vertices, it requests a lock on their LGCA. Since threads hold at most one lock at any given time, deadlocks never occur.

The absence of deadlocks combined with the guaranteed progress of threads ensures that CALock is live.

### C. Fairness

When a thread requests a lock, the lock is granted after a defined number of blocks. The lock acquisition algorithm does not lead to a starvation of threads.

**Discussion:** CALock uses an FCFS mechanism to grant locks. When a thread is blocked, it is always blocked by a thread with a lower sequence number. A thread can be blocked and bypassed by other threads in the presence of conflicts at most $n$ times ($n$ is the size of the lock pool). Since sequence numbers are assigned atomically and are monotonically increasing, a thread is granted its lock after at most $n$ bypasses. After a thread is bypassed $n$ times, the sequence number of that blocked thread would be the lowest, and it would be granted the lock it requested. This ensures that no thread starves and CALock is fair.

## VII. COMPLEXITY ANALYSIS OF CALOCK

<table><caption>TABLE I: Time complexities of the labelling in CALock</caption><thead><tr><th></th><th>Average Case</th><th>Best Case</th><th>Worst case</th></tr></thead><tbody><tr><td>Labelling</td><td>θ(v<sup>2</sup> + <sup>v<sup>2</sup></sup>&frasl;<sub>d<sub>avg</sub></sub>)</td><td>Ω(1)</td><td>O(v<sup>2</sup>)</td></tr><tr><td>LGCA computation</td><td>θ(<sup>s,v</sup>&frasl;<sub>d<sub>avg</sub></sub>)</td><td>Ω(1)</td><td>O(<sup>v<sup>2</sup></sup>&frasl;<sub>d<sub>avg</sub></sub>)</td></tr><tr><td>Conflict detection</td><td>θ(n)</td><td>Ω(1)</td><td>O(n)</td></tr></tbody></table>

The labelling algorithm involves two operations.

* **Traversal:** Recursive BFS over the graph starting from the root. The number of edges examined is dependent on the average degree of vertices. In the worst case, where the graph is complete, the degree of any vertex is the number of vertices in the graph.

* **Label computation:** For each vertex, the intersection of its parents' labels needs to be calculated. The number of elements in the label of a vertex is inversely proportional to the number of its parents. A vertex with more parents has more paths from the root and, hence, a smaller label. We can approximate this in terms of the vertex degree as well.

For a graph $G = (V, E)$, let $v = |V|$ be the number of vertices, $e = |E|$ be the number of edges and $d_{avg}$ be the average degree of a vertex. According to the Handshake lemma [18], the average degree of a vertex is

$$d_{avg} = \frac{2 \times e}{v} \qquad (3)$$

The complexity of breadth-first traversal is $\theta(v + v \cdot d_{avg})$. For each vertex, the size of its label is inversely proportional to the number of parents it has, and consequently, label computation is inversely proportional to the average degree, i.e. $\theta(v/d_{avg})$.

The combined complexity of these operations for the initial labelling is $\theta(v^2 + \frac{v^2}{d_{avg}})$.

In the best case, the graph contains only one vertex. The best case complexity is $\Omega(1)$. In the worst case, the average
degree of vertices is 1. Thus, the worst-case complexity is $O(v^2)$.

When a thread requests a lock, it finds the LGCA of the lock targets and issues a lock request. The LGCA is computed via a set intersection of the labels of the lock targets. If the lock request is for *s* lock targets and the average label size is $\theta(\frac{v}{d_{avg}})$, the complexity of finding the lock guard is $\theta(\frac{s \cdot v}{d_{avg}})$. In the best case, the lock request is for a single vertex and the complexity is $\Omega(1)$. In the worst case, the lock request is for all vertices of the graph, and the complexity is $O(\frac{v^2}{d_{avg}})$.

These labels are then used to detect conflicts. A thread checks conflicts with all other threads, i.e. *n* times. For each conflict, a set membership test is performed. An efficient set implementation can test the membership in $O(1)$. The complexity of conflict detection is $\theta(n)$.

## VIII. EXPERIMENTAL EVALUATION

With benchmark experiments, we evaluate the performance of CALock and compare it with the state of the art against several parameters. Our evaluation uses the same benchmark experiments as DomLock [7], MID [8] and FlexiGran [12] i.e. STMBench7 [10].

We run our experiments on a machine with an AMD EPYC 7642 CPU with 48 Cores, a base clock of 2.3 GHz and 512 GB of RAM. The benchmark is deployed on a Docker container under Ubuntu 20.04. GCC 12.1 and CMake 3.22 are used to build the benchmark. The compilation is done at the C++ 26 standard to utilise atomic conditional wait semantics.

### A. STMBench7

STMBench is a well-known benchmark based on the classical OO7 object-oriented benchmark suite [19]. It is used to evaluate the performance of hierarchical algorithms and data structures [7], [8], [12], [20]–[29].

The graph in STMBench7, as represented in Figure 5, consists of a *design root*, which in turn consists of several levels of *complex assemblies*. Each of the deepest complex assemblies consists of a set of *base assemblies*. A *composite part* can be contained in several base assemblies. Each composite part contains a set of *atomic parts*. These atomic parts form a near-complete graph. The root of this graph is connected to a single composite part.

<table><caption>TABLE II: Sizes of the STMBench7 hierarchies</caption><thead><tr><td>Graph Size</td><td>Vertices</td><td>Edges</td></tr></thead><tbody><tr><td>Small</td><td>234,737</td><td>4,393,682</td></tr><tr><td>Medium</td><td>2,334,257</td><td>43,759,682</td></tr><tr><td>Large</td><td>23,329,457</td><td>437,419,682</td></tr></tbody></table>

STMBench7 provides three sizes of hierarchies. Table II shows the number of vertices and edges in each hierarchy size. Unless stated specifically, benchmarks are run on the large hierarchy.

STMBench7 provides coarse-grain and medium-grain lock implementations. These are representatives of fixed granularity locking techniques that are used in practice. The coarse lock is a reader-writer lock on the entire graph. Figure 5 shows the

medium lock grains for a module. A single lock guards each level of complex assemblies. Deeper in the graph, the atomic parts are guarded by their own lock. Structural modification operations take a mutex on the entire graph.

<figure><img src="image_5.png" /><figcaption>Fig. 5: Structure of STMBench graph with medium-grain lock grains</figcaption></figure>

### B. Metadata management: bulk labelling and relabelling

1) **Bulk labelling:** We measure the time it takes to assign the labels to a graph when it is first created. This simulates loading data into a database. Coarse-grain, medium-grain, and intention locks do not need labelling. For the other techniques, this time, it is measured for three different sizes of the STMBench7 graph. The results are shown in Figure 6. DomLock is the fastest since a single depth-first-traversal is sufficient to compute the intervals. MID is slower than DomLock because it needs to compute a pair of intervals for each vertex. The first by a depth-first traversal and the second by a depth-first traversal on the mirror image of the graph. FlexiGran is faster than DomLock but slower than MID because of the additional level information that needs to be computed per vertex.

CALock labels take the longest to compute for a new hierarchy since a recursive breadth-first traversal with a fix-point dependent on the number of paths to a vertex from the root defines them.

2) **Relabelling:** Figure 7 shows the average time spent relabelling the graph per structural modification. Coarse-grain, medium-grain, and intention locks do not have additional

<figure><img src="image_6.png" /><figcaption>Fig. 6: Time to compute initial labels (lower is better)</figcaption></figure>
metadata and hence do not require relabelling. In CALock, relabelling is significantly faster than in DomLock, MID, and FlexiGran. This is because with DomLock, MID and FlexiGran, a structural modification anywhere in the graph changes the post-order traversal order of several vertices. A change in this traversal order requires recomputing many intervals which propagate to the root of the hierarchy. Since the root is involved in the relabelling, intervals are computed under a mutex on the graph, which prevents parallel relabelling of disjoint subgraphs, leading to poor performance.

In contrast, CALock only relabels the subgraph directly affected by a structural modification. Since CALock labels always propagate towards the leaves, they are computed under the lock acquired to perform the structural modification. Thus, multiple grains can be locked, modified and relabelled in parallel. CALock is 100 times faster at relabelling than DomLock, MID and FlexiGran, as shown in Figure 7.

<figure><img src="image_7.png" /><figcaption>Fig. 7: Time spent relabelling the graph per modification operation (lower is better)</figcaption></figure>

### C. Metadata size in memory

All MGL techniques utilise metadata to identify the lock grains. DomLock uses an integer range per vertex as a label, requiring less memory due to its compact representation. MID uses two integer ranges per vertex. FlexiGran uses the DomLock intervals and an integer to store the level of a vertex. In contrast, CALock employs sets of vertex identifiers (integers) as labels. As shown in Figure 8, CALock's metadata consumes approximately 1.5 times more memory than DomLock, MID and FlexiGran. In DomLock, MID and FlexiGran, regardless of the graph's topology, the label at each vertex consists of at most two integer ranges, i.e. 4 integers. This has low memory requirement; however, the information about the exact topology of the graph is lost, leading to false subsumptions (Section VIII-D). CALock labels, being sets, contain more information, allowing for smaller grain sizes and preventing the problem of false subsumptions, allowing a greater degree of parallelism.

### D. Lock granularity and false subsumptions

Locking a vertex in MGL implicitly locks all other vertices in the lock grain. We measure the number of targets implicitly locked for every guard vertex in the STMBench7 graph to compare the grain size. Figure 9 compares the granularity of DomLock, MID, FlexiGran and CALock.

<figure><img src="image_8.png" /><figcaption>Fig. 8: Size of the metadata used for labelling (lower is better)</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 9: Vertices locked per vertex type (lower is better)</figcaption></figure>

Locking an atomic part has almost the same effect for all techniques, with CALock being marginally better and reducing grain sizes. This is because, in STMBench7, the atomic parts are strongly connected and locking a single vertex often causes the whole graph of atomic parts to be locked. When locking higher up in the graph, the effects vary. Locking a complex assembly is more expensive with intervals from DomLock, MID and FlexiGran because complex assemblies often share composite parts, leading to large grains due to false subsumptions. When locking base assemblies with DomLock, MID and FlexiGran, multiple base assemblies are locked due to the one-to-many relationship between base assemblies and composite parts due to false subsumptions.

The granularity of the lock and its effect on subsumption is highly dependent on the topology of the graph. False subsumptions aggravate the problem of large grains and lead to more grain overlaps between threads. The grain sizes of CALock are always smaller than other locking techniques, allowing for more parallelism and better overall performance.

### E. Overall locking performance

Sections VIII-B, VIII-C and VIII-D study individual parameters in isolation. Now, we study all of them together and evaluate their effects on the overall performance of the locking techniques. For FlexiGran, the percentage of fine-grain locks is set to 50% as recommended by the authors in their paper [12]. In this set of benchmarks, we study static and dynamic graphs in STMBench under the same workloads. Figure 10 shows the throughput of different workloads and locking techniques on static graphs and dynamic graphs. The charts in these figures are plotted with the number of concurrent threads on the x-axis and the throughput (op/s) or response time (µs) on the y-axis. Response time is measured from when the thread issues a lock request until the lock is granted.
<figure><img src="image_10.png" /><figcaption>Fig. 10: Performance with different workload types (R: reads, W: writes, SM: structural modifications)</figcaption></figure>

1) **Static Graphs**: Throughput figures 10a, 10b and 10c show that coarse-grain and medium-grain locks perform the best for up to 4 concurrent threads due to the additional computation of the lock grain required for DomLock, MID, FlexiGran and CALock. Beyond 4 threads, some MGL techniques give better throughput. However, the performance of DomLock and MID stagnates at 8 threads.

The graph in STMBench is irregular and has multiple paths leading to a vertex. Due to this, the lock grain sizes are uneven, and DomLock, MID and FlexiGran intervals often lead to false subsumptions, which block a thread even when there is no conflict (see Section VIII-D). Intention locks often deadlock due to these irregular paths leading to poor performance.

CALock successfully minimises the size of the lock grains and allows threads to lock disjoint grains in parallel, achieving better scalability than intention locks, DomLock, MID and FlexiGran. We observe that CALock is at least 2 times faster with 32 threads and 4.5 times faster with 64 threads than any other locking technique.

Response time figures 10g, 10h, 10i show that between MGL techniques, FlexiGran and Intention locks, on average, take the longest to grant a lock. With intention locks, this is because of the expensive traversals required to place intention tags on vertices. With FlexiGran, lock conflict detection is costly because of the coexistence of MGL and fine-grain locks. DomLock and MID are faster than FlexiGran but are at least 2 times slower than CALock.

In interval-based MGL techniques like DomLock, MID and

FlexiGran, once a thread identifies an interval it wishes to lock, it traverses the hierarchy to find the lock guard, which is a vertex with the requested interval (resp. interval pair for MID). This traversal is especially expensive when locking deeper in the hierarchy. CALock avoids traversals altogether by using a set intersection to find the LGCA, which is the ID of the guard vertex, thereby giving faster response times for lock requests.

2) **Dynamic Graphs**: With structural modifications, the topology of the graph changes, triggering a relabelling step in DomLock, MID, FlexiGran and CALock. Structural modifications happen under a graph mutex for coarse-grain locks, medium-grain locks, DomLock, MID and FlexiGran. Throughput figures 10d, 10e, and 10f show the performance of locking algorithms under reads and writes that interleave with structural modifications leading to relabelling of the graph. In these workloads, 1% of the total writes are structural modifications. In write-heavy workloads (Throughput figure 10f), structural modifications can be as high as 0.9%. While in read-heavy workloads (Throughput figure 10d), they are as low as 0.1%. Even under a small load of structural modifications, we observe that coarse-grain and medium-grain locks do not scale well as the number of threads increases. Intention locks are no different. While structural modifications do not require additional care in intention locks, the cost of placing intention tags on all vertices is very high.

DomLock, MID and FlexiGran perform significantly worse compared to other algorithms because along with the lack of parallelism due to false subsumptions, an additional relabelling
step for each structural modification performed under a mutex. This effect is shown in the curves in Throughput figures 10d, 10e and 10f for DomLock, MID and FlexiGran, which are relatively flat and close to 0, indicating a lack of performance and scalability. CALock can parallelise structural modifications and is 2 times faster than coarse and medium-grained locks and about 8 times faster than Intention locks, DomLock, MID and FlexiGran.

Response time for Intention locks remains the same regardless of the proportion of structural modifications. However, as shown in Response time figures 10j, 10k and 10l, response time for DomLock, MID and FlexiGran is longer for workloads with structural modifications compared to workloads without. Response time for CALock also increases for dynamic graphs compared to static graphs, but CALock remains faster than all other lock techniques for even the most contended workload.

## F. Summary of experimental results

**Discussion:** The initial labelling time is proportional to the size of the graph. Still, in conjunction with other benchmark results, CALock is a better choice for runtime performance since the integer labels of DomLock, MID and FlexiGran require expensive relabelling when structural modifications occur (see Section VIII-B).

**Summary:** With the results from the experiments using STMBench7, we can draw the following conclusions.

* Intention locks are the most expensive locking technique for any workload and are unsuitable for irregular graphs.

* CALock is faster than DomLock, coarse-grain and medium-grain locks for any workload that involves more than 8 concurrent threads.

* In workloads with low contention on static graphs, CALock is at least 3 times faster than any other locking technique.

* In workloads with low contention on dynamic graphs, CALock is 1.5 times faster than coarse-grain and medium-grain locks and 8x faster than other MGL techniques.

* In workloads with high contention on static graphs, CALock is 2 times faster than coarse-grained and medium-grained locks and 4 times faster than other MGL techniques.

* In workloads with high contention and dynamic graphs, CALock performs as good as coarse-grain and medium-grain locks and is 4 times faster than other MGL techniques.

* CALock is an appropriate locking technique if the graph is irregular and dynamic (which makes intention locks, DomLock, MID and FlexiGran unsuitable).

# IX. CONCLUSION AND FUTURE WORK

In this paper, we presented the definition and proof as well as the implementation and benchmark of CALock. CALock is a multi-granularity locking technique that exploits the guarding ancestors of vertices in a graph to identify the

lock grain for a lock request. The implementation and claims are supported by the benchmarks using STMBench7. Path-based locking schemes without additional metadata, i.e. Intention locks, perform poorly on irregular graphs. Interval-based schemes like DomLock, MID, and FlexiGran perform better but suffer from false subsumptions. In addition, these intervals are expensive to maintain. CALock is a better choice for irregular graphs and offers better performance for both parallel processing and maintaining labels when the graph mutates. In CALock, a thread can hold a single lock at a time. We are working on implementing a 2PL mechanism with CALock that will allow threads to grow their grains dynamically. Further, CALock labels can use topological compression by representing parts of the label with an identifier for a graph component. This will reduce the memory footprint of the labels and make CALock even more competitive.

# REFERENCES

[1] Oracle, "Database concepts- logical structures," Dec 2023. [Online]. Available: https://docs.oracle.com/en/database/oracle/oracle-database/23/cncpt/logical-storage-structures.html

[2] M. D. Jacyntho and D. Schwabe, "A multigranularity locking model for RDF," *J. Web Semant.*, vol. 39, pp. 25–46, 2016. [Online]. Available: https://doi.org/10.1016/j.websem.2016.05.002

[3] D. Lomet and M. F. Mokbel, "Locking key ranges with unbundled transaction services," *Proc. VLDB Endow.*, vol. 2, no. 1, p. 265–276, aug 2009. [Online]. Available: https://doi.org/10.14778/1687627.1687658

[4] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger, "The notions of consistency and predicate locks in a database system," *Commun. ACM*, vol. 19, no. 11, p. 624–633, nov 1976. [Online]. Available: https://doi.org/10.1145/360363.360369

[5] D. R. Ries and M. Stonebraker, "Effects of locking granularity in a database management system," *ACM Trans. Database Syst.*, vol. 2, no. 3, pp. 233–246, 1977. [Online]. Available: https://doi.org/10.1145/320557.320566

[6] J. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger, "Granularity of locks in a large shared data base," in *Proceedings of the International Conference on Very Large Data Bases, September 22-24, 1975*, Framingham, Massachusetts, USA, D. S. Kerr, Ed. ACM, 1975, pp. 428–451. [Online]. Available: https://doi.org/10.1145/1282480.1282513

[7] S. Kalikar and R. Nasre, "Domlock: a new multi-granularity locking technique for hierarchies," in *Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016, Barcelona, Spain, March 12-16, 2016*, R. Asenjo and T. Harris, Eds. ACM, 2016, pp. 23:1–23:12. [Online]. Available: https://doi.org/10.1145/2851141.2851164

[8] M. A. Anju and R. Nasre, "Multi-interval domlock: Toward improving concurrency in hierarchies," *ACM Trans. Parallel Comput.*, vol. 9, no. 3, pp. 12:1–12:27, 2022. [Online]. Available: https://doi.org/10.1145/3543543

[9] S. Kalikar and R. Nasre, "Toggle: Contention-aware task scheduler for concurrent hierarchical operations," in *Euro-Par 2019: Parallel Processing - 25th International Conference on Parallel and Distributed Computing, Göttingen, Germany, August 26-30, 2019*, Proceedings, ser. Lecture Notes in Computer Science, R. Yahyapour, Ed., vol. 11725. Springer, 2019, pp. 142–155. [Online]. Available: https://doi.org/10.1007/978-3-030-29400-7_11

[10] R. Guerraoui, M. Kapalka, and J. Vitek, "Stmbench7: a benchmark for software transactional memory," in *Proceedings of the 2007 EuroSys Conference, Lisbon, Portugal, March 21-23, 2007*, P. Ferreira, T. R. Gross, and L. Veiga, Eds. ACM, 2007, pp. 315–324. [Online]. Available: https://doi.org/10.1145/1272996.1273029

[11] "Transaction locking and row versioning guide - sql server," Dec 2022. [Online]. Available: https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-transaction-locking-and-row-versioning-guide?source= recommendations%3bview%3dsql-server-ver16#lock&modes
[12] A. Mongandampulath Akathott and R. Nasre, "Flexigran: Flexible granularity locking in hierarchies," in *Euro-Par 2024: Parallel Processing*, J. Carretero, S. Shende, J. Garcia-Blas, I. Brandic, K. Olcoz, and M. Schreiber, Eds. Cham: Springer Nature Switzerland, 2024, pp. 3–17.

[13] J. Fischer and D. H. Huson, "New common ancestor problems in trees and directed acyclic graphs," *Inf. Process. Lett.*, vol. 110, no. 8-9, pp. 331–335, 2010. [Online]. Available: https://doi.org/10.1016/j.ipl.2010.02.014

[14] M. Sharir, "A strong-connectivity algorithm and its applications in data flow analysis," *Computers & Mathematics with Applications*, vol. 7, no. 1, pp. 67–72, 1981.

[15] R. E. Tarjan, "Depth-first search and linear graph algorithms," *SIAM J. Comput.*, vol. 1, no. 2, pp. 146–160, 1972. [Online]. Available: https://doi.org/10.1137/0201010

[16] J. Cheriyan and K. Mehlhorn, "Algorithms for dense graphs and networks on the random access computer," *Algorithmica*, vol. 15, no. 6, pp. 521–549, 1996. [Online]. Available: https://doi.org/10.1007/BF01940880

[17] T. Grauman, S. G. Hartke, A. S. Jobson, W. B. Kinnersley, D. B. West, L. Wiglesworth, P. Worah, and H. Wu, "The hub number of a graph," *Inf. Process. Lett.*, vol. 108, no. 4, pp. 226–228, 2008. [Online]. Available: https://doi.org/10.1016/j.ipl.2008.05.022

[18] L. Euler, "Solutio problematis ad geometriam situs pertinentis," *Commentarii academiae scientiarum Petropolitanae*, pp. 128–140, 1741.

[19] M. J. Carey, D. J. DeWitt, and J. F. Naughton, "The oo7 benchmark," in *Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data*, Washington, DC, USA, May 26-28, 1993, P. Buneman and S. Jajodia, Eds. ACM Press, 1993, pp. 12–21. [Online]. Available: https://doi.org/10.1145/170035.170041

[20] A. Prokopec, A. Rosà, D. Leopoldseder, G. Duboscq, P. Tùma, M. Studener, L. Bulej, Y. Zheng, A. Villazón, D. Simon, T. Würthinger, and W. Binder, "Renaissance: benchmarking suite for parallel applications on the JVM," in *Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation*, ser. PLDI 2019. New York, NY, USA: Association for Computing Machinery, Jun. 2019, pp. 31–47. [Online]. Available: https://dl.acm.org/doi/10.1145/3314221.3314637

[21] T. M. Vale, J. A. Silva, R. J. Dias, and J. M. Lourenço, "Pot: Deterministic Transactional Execution," *ACM Transactions on Architecture and Code Optimization*, vol. 13, no. 4, pp. 1–24, Dec. 2016. [Online]. Available: https://dl.acm.org/doi/10.1145/3017993

[22] P. Felber, S. Issa, A. Matveev, and P. Romano, "Hardware read-write lock elision," in *Proceedings of the Eleventh European Conference on Computer Systems*. London United Kingdom: ACM, Apr. 2016, pp. 1–15. [Online]. Available: https://dl.acm.org/doi/10.1145/2901318.2901346

[23] F. M. Carvalho and J. Cachopo, "Optimizing memory transactions for large scale programs," *Journal of Parallel and Distributed Computing*, vol. 89, pp. 13–24, Mar. 2016. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0743731515002099

[24] J. Kim, R. Palmieri, and B. Ravindran, "On Scheduling in Distributed Transactional Memory: Techniques and Tradeoffs," in *Handbook on Data Centers*, S. U. Khan and A. Y. Zomaya, Eds. New York, NY: Springer, 2015, pp. 1267–1283. [Online]. Available: https://doi.org/10.1007/978-1-4939-2092-1_44

[25] R. Filipe and J. Barreto, "Nested Parallelism in Transactional Memory," in *Transactional Memory. Foundations, Algorithms, Tools, and Applications: COST Action Euro-TM IC1001*, R. Guerraoii and P. Romano, Eds. Cham: Springer International Publishing, 2015, pp. 192–209. [Online]. Available: https://doi.org/10.1007/978-3-319-14720-8_9

[26] H. Rito and J. Cachopo, "ProPS: A Progressively Pessimistic Scheduler for Software Transactional Memory," in *Euro-Par 2014 Parallel Processing*, F. Silva, I. Dutra, and V. Santos Costa, Eds. Cham: Springer International Publishing, 2014, pp. 150–161.

[27] S. Kalikar and R. Nasre, "Numlock: Towards optimal multi-granularity locking in hierarchies," in *Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018, Eugene, OR, USA, August 13-16, 2018*. ACM, 2018, pp. 75:1–75:10. [Online]. Available: https://doi.org/10.1145/3225058.3225141

[28] K. Ganesh, S. Kalikar, and R. Nasre, "Multi-granularity locking in hierarchies with synergistic hierarchical and fine-grained locks," in *Euro-Par 2018: Parallel Processing - 24th International Conference on Parallel and Distributed Computing, Turin, Italy, August 27-31, 2018, Proceedings*, ser. Lecture Notes in Computer Science, M. Aldinucci, L. Padovani, and M. Torquati, Eds., vol. 11014. Springer, 2018, pp. 546–559. [Online]. Available: https://doi.org/10.1007/978-3-319-96983-1_39

[29] P. Liu and C. Zhang, "Unleashing concurrency for irregular data structures," in *36th International Conference on Software Engineering, ICSE '14, Hyderabad, India - May 31 - June 07, 2014*, P. Jalote, L. C. Briand, and A. van der Hoek, Eds. ACM, 2014, pp. 480–490. [Online]. Available: https://doi.org/10.1145/2568225.2568277