{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:32:48Z","timestamp":1753439568495,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            Locking has been a predominant technique depended upon for achieving thread synchronization and ensuring correctness in multi-threaded applications. It has been established that the concurrent applications working with hierarchical data witness significant benefits due to multi-granularity locking (MGL) techniques compared to either fine- or coarse-grained locking. The\n            <jats:italic>de facto<\/jats:italic>\n            MGL technique used in hierarchical databases is\n            <jats:italic>intention locks<\/jats:italic>\n            , which uses a traversal-based protocol for hierarchical locking. A recent MGL implementation, dominator-based locking (DomLock), exploits interval numbering to balance the locking cost and concurrency and outperforms intention locks for non-tree-structured hierarchies. We observe, however, that depending upon the hierarchy structure and the interval numbering, DomLock pessimistically declares subhierarchies to be locked when in reality they are not. This increases the waiting time of locks and, in turn, reduces concurrency. To address this issue, we present Multi-Interval DomLock (MID), a new technique to improve the degree of concurrency of interval-based hierarchical locking. By adding additional intervals for each node,\n            <jats:sc>MID<\/jats:sc>\n            helps in reducing the unnecessary lock rejections due to false-positive lock status of sub-hierarchies. Unleashing the hidden opportunities to exploit more concurrency allows the parallel threads to finish their operations quickly, leading to notable performance improvement. We also show that with sufficient number of intervals,\n            <jats:sc>MID<\/jats:sc>\n            can avoid all the lock rejections due to false-positive lock status of nodes.\n            <jats:sc>MID<\/jats:sc>\n            is general and can be applied to any arbitrary hierarchy of trees,\n            <jats:bold>Directed Acyclic Graphs (DAGs)<\/jats:bold>\n            , and cycles. It also works with dynamic hierarchies wherein the hierarchical structure undergoes updates. We illustrate the effectiveness of\n            <jats:sc>MID<\/jats:sc>\n            using STMBench7 and, with extensive experimental evaluation, show that it leads to significant throughput improvement (up to 141%, average 106%) over DomLock.\n          <\/jats:p>","DOI":"10.1145\/3543543","type":"journal-article","created":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T09:04:34Z","timestamp":1657271074000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Multi-Interval DomLock: Toward Improving Concurrency in Hierarchies"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5116-1109","authenticated-orcid":false,"given":"M. A.","family":"Anju","sequence":"first","affiliation":[{"name":"IIT Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7490-625X","authenticated-orcid":false,"given":"Rupesh","family":"Nasre","sequence":"additional","affiliation":[{"name":"IIT Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Synchronization Costs in Parallel Programs and Concurrent Data Structures","author":"Aksenov Vitalii","year":"2018","unstructured":"Vitalii Aksenov. 2018. Synchronization Costs in Parallel Programs and Concurrent Data Structures. Ph.D. Dissertation. ITMO University, Paris Diderot University."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/588058.588079"},{"key":"e_1_3_2_4_2","volume-title":"The Performance of Concurrency Control Algorithms for Database Management Systems","author":"Carey Michael J.","year":"1984","unstructured":"Michael J. Carey. 1984. The Performance of Concurrency Control Algorithms for Database Management Systems. Technical Report. University of Wisconsin\u2013Madison Department of Computer Sciences."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170041"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1563"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375619"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2004.12.002"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404397.3404398"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96983-1_39"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/971701.50206"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_10"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1282480.1282513"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273029"},{"key":"e_1_3_2_16_2","first-page":"336","volume-title":"European Symposium on Programming","author":"Hawkins Peter","year":"2012","unstructured":"Peter Hawkins, Alex Aiken, Kathleen Fisher, Martin Rinard, and Mooly Sagiv. 2012. Reasoning about lock placements. In European Symposium on Programming. Springer, Cham, 336\u2013356."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3016078.2851164"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3127584"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225141"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29400-7_11"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415544"},{"key":"e_1_3_2_22_2","unstructured":"Linux. 2022. Sequence Counters and Sequential Locks. Retrieved January 20 2022 from https:\/\/www.kernel.org\/doc\/html\/latest\/locking\/seqlock.html."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568277"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687658"},{"key":"e_1_3_2_25_2","volume-title":"Key Range Locking Strategies for Improved Concurrency","author":"Lomet David B.","year":"1993","unstructured":"David B. Lomet. 1993. Key Range Locking Strategies for Improved Concurrency. Digital Equipment Corporation, Cambridge Research Laboratory, UK."},{"key":"e_1_3_2_26_2","unstructured":"M. A. Anju and Rupesh Nasre. 2022. Multi-Interval DomLock. Retrieved from https:\/\/bitbucket.org\/msdanju\/open-mid\/src\/master\/."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809990"},{"key":"e_1_3_2_28_2","unstructured":"Microsoft. 2021. Azure SQL. Retrieved September 1 2021 from https:\/\/docs.microsoft.com\/en-us\/azure\/azure-sql\/."},{"key":"e_1_3_2_29_2","unstructured":"Microsoft. 2021. SQL Server 2019. Retrieved September 1 2021 from https:\/\/www.microsoft.com\/en-in\/sql-server\/sql-server-2019."},{"key":"e_1_3_2_30_2","unstructured":"Microsoft. 2021. Transaction Locking and Row Versioning Guide. Retrieved September 1 2021 from https:\/\/docs.microsoft.com\/en-us\/sql\/relational-databases\/sql-server-transaction-locking-and-row-versioning-guide?view=sql-server-ver15."},{"key":"e_1_3_2_31_2","unstructured":"Oracle. 2021. Oracle Database 21c. Retrieved July 1 2021 from https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/21\/index.html."},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1145\/3226595.3226640","volume-title":"Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker","author":"Stonebraker Michael","year":"2018","unstructured":"Michael Stonebraker, Eugene Wong, Peter Kreps, and Gerald Held. 2018. The design and implementation of INGRES. In Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker. ACM, New York, NY, 561\u2013605."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICOEI48184.2020.9142943"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2019.00004"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/96068"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00061"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543543","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543543","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:47Z","timestamp":1750186847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543543"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3543543"],"URL":"https:\/\/doi.org\/10.1145\/3543543","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"2021-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}