{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:09Z","timestamp":1773481989478,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Substantial research efforts have been devoted to studying the performance optimality problem for distributed database transactions. However, they focus just on optimizing transactional reads, and thus overlook crucial factors, such as the efficiency of writes, which also impact the overall system performance. Motivated by a recent study on Twitter's workloads showing the prominence of write-heavy workloads in practice, we make a substantial step towards performance-optimal distributed transactions by also aiming to optimize writes, a fundamentally new dimension to this problem. We propose a new design objective and establish impossibility results with respect to the achievable isolation levels. Guided by these results, we present two new transaction algorithms with different isolation guarantees that fulfill this design objective. Our evaluation demonstrates that these algorithms outperform the state of the art.<\/jats:p>","DOI":"10.1145\/3639264","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-25","source":"Crossref","is-referenced-by-count":6,"title":["NOC-NOC: Towards Performance-optimal Distributed Transactions"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3578-7432","authenticated-orcid":false,"given":"Si","family":"Liu","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1393-4732","authenticated-orcid":false,"given":"Luca","family":"Multazzu","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0427-9710","authenticated-orcid":false,"given":"Hengfeng","family":"Wei","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2952-939X","authenticated-orcid":false,"given":"David A.","family":"Basin","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"e_1_2_2_2_1","volume-title":"Preguicc a, and Marc Shapiro","author":"Akkoorath Deepthi Devaki","year":"2016","unstructured":"Deepthi Devaki Akkoorath, Alejandro Z. Tomsic, Manuel Bravo, Zhongmiao Li, Tyler Crain, Annette Bieniusa, Nuno M. Preguicc a, and Marc Shapiro. 2016. Cure: Strong Semantics Meets High Availability and Low Latency. In ICDCS 2016. IEEE Computer Society, 405--414."},{"key":"e_1_2_2_3_1","volume-title":"The Impossibility of Fast Transactions. In IPDPS'20","author":"Antoniadis Karolos","year":"2020","unstructured":"Karolos Antoniadis, Diego Didona, Rachid Guerraoui, and Willy Zwaenepoel. 2020. The Impossibility of Fast Transactions. In IPDPS'20. IEEE, 1143--1154."},{"key":"e_1_2_2_4_1","unstructured":"Masoud Saeida Ardekani Pierre Sutra Nuno Pregui\u00e7a and Marc Shapiro. 2013. Non-Monotonic Snapshot Isolation. arxiv: 1306.3906 [cs.DC]"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2909870"},{"key":"e_1_2_2_6_1","volume-title":"O'Neil","author":"Berenson Hal","year":"1995","unstructured":"Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, and Patrick E. O'Neil. 1995. A Critique of ANSI SQL Isolation Levels. In SIGMOD'95. ACM Press, 1--10."},{"key":"e_1_2_2_7_1","volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein Philip A.","unstructured":"Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley."},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Eric A. Brewer. 2000. Towards robust distributed systems (abstract). In PODC. 7.","DOI":"10.1145\/343477.343502"},{"key":"e_1_2_2_9_1","volume-title":"ATC'13","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkateshwaran Venkataramani. 2013. TAO: Facebook's Distributed Data Store for the Social Graph. In ATC'13. USENIX Association, 49--60."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236209"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538616"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476379"},{"key":"e_1_2_2_13_1","volume-title":"Lazy Database Replication with Ordering Guarantees. In ICDE","author":"Daudjee Khuzaima","year":"2004","unstructured":"Khuzaima Daudjee and Kenneth Salem. 2004. Lazy Database Replication with Ordering Guarantees. In ICDE 2004. IEEE Computer Society, 424--435."},{"key":"e_1_2_2_14_1","volume-title":"Distributed Transactional Systems Cannot Be Fast. In SPAA'19","author":"Didona Diego","year":"2019","unstructured":"Diego Didona, Panagiota Fatourou, Rachid Guerraoui, Jingjing Wang, and Willy Zwaenepoel. 2019. Distributed Transactional Systems Cannot Be Fast. In SPAA'19. ACM, 369--380."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236210"},{"key":"e_1_2_2_16_1","first-page":"1","article-title":"GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks. In SoCC 2014","volume":"4","author":"Du Jiaqing","year":"2014","unstructured":"Jiaqing Du, Calin Iorgulescu, Amitabha Roy, and Willy Zwaenepoel. 2014. GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks. In SoCC 2014. ACM, 4:1--4:13.","journal-title":"ACM"},{"key":"e_1_2_2_17_1","volume-title":"The Design and Operation of CloudLab. In ATC'19","author":"Duplyakin Dmitry","year":"2019","unstructured":"Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of CloudLab. In ATC'19. USENIX Association, 1--14."},{"key":"e_1_2_2_18_1","volume-title":"Accessed","author":"SQL.","year":"2023","unstructured":"ElectricSQL. Accessed in July, 2023. https:\/\/electric-sql.com\/."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","unstructured":"Shabnam Ghasemirad. 2022. Mechanized Data Consistency Models for Distributed Database Transactions. Master's thesis. ETH Zurich. https:\/\/doi.org\/10.3929\/ethz-b-000581334.","DOI":"10.3929\/ethz-b-000581334"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_2_21_1","volume-title":"PODC'11","author":"Golab Wojciech","unstructured":"Wojciech Golab, Xiaozhou Li, and Mehul A. Shah. 2011. Analyzing consistency properties for fun and profit. In PODC'11. ACM, 197--206."},{"key":"e_1_2_2_22_1","volume-title":"Regular Sequential Serializability and Regular Sequential Consistency. In SOSP'21","author":"Helt Jeffrey","year":"2021","unstructured":"Jeffrey Helt, Matthew Burke, Amit Levy, and Wyatt Lloyd. 2021. Regular Sequential Serializability and Regular Sequential Consistency. In SOSP'21. ACM, 163--179."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_2_2_24_1","volume-title":"Lynch","author":"Konwar Kishori M.","year":"2021","unstructured":"Kishori M. Konwar, Wyatt Lloyd, Haonan Lu, and Nancy A. Lynch. 2021. SNOW Revisited: Understanding When Ideal READ Transactions Are Possible. In IPDPS'21. IEEE, 922--931."},{"key":"e_1_2_2_25_1","volume-title":"Sturgis","author":"Lampson Butler","year":"1979","unstructured":"Butler Lampson and Howard E. Sturgis. 1979. Crash recovery in a distributed storage system. Xerox Palo Alto Research Center."},{"key":"e_1_2_2_26_1","volume-title":"Andersen","author":"Lim Hyeontaek","year":"2017","unstructured":"Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. 2017. Cicada: Dependably Fast Multi-Core In-Memory Transactions. In SIGMOD '17. ACM, 21--35."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494517"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Si Liu Luca Multazzu Hengfeng Wei and David Basin. 2023. Artifact and technical report for \u201cNOC-NOC: Towards Performance-optimal Distributed Transactions\u201d. https:\/\/github.com\/siliunobi\/NOC-NOC.","DOI":"10.1145\/3639264"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851613.2851838"},{"key":"e_1_2_2_30_1","volume-title":"SOSP","author":"Lloyd Wyatt","year":"2011","unstructured":"Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In SOSP 2011. ACM, 401--416."},{"key":"e_1_2_2_31_1","volume-title":"Andersen","author":"Lloyd Wyatt","year":"2013","unstructured":"Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2013. Stronger Semantics for Low-Latency Geo-Replicated Storage. In NSDI'13. USENIX Association, 313--328."},{"key":"e_1_2_2_32_1","volume-title":"The SNOW Theorem and Latency-Optimal Read-Only Transactions. In OSDI'16","author":"Lu Haonan","year":"2016","unstructured":"Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd. 2016. The SNOW Theorem and Latency-Optimal Read-Only Transactions. In OSDI'16. USENIX Association, 135--150."},{"key":"e_1_2_2_33_1","volume-title":"OSDI'23","author":"Lu Haonan","year":"2023","unstructured":"Haonan Lu, Shuai Mu, Siddhartha Sen, and Wyatt Lloyd. 2023. NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall. In OSDI'23. USENIX Association, 305--323."},{"key":"e_1_2_2_34_1","volume-title":"Performance-Optimal Read-Only Transactions. In OSDI'20","author":"Lu Haonan","year":"2020","unstructured":"Haonan Lu, Siddhartha Sen, and Wyatt Lloyd. 2020a. Performance-Optimal Read-Only Transactions. In OSDI'20. USENIX Association, 333--349."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815426"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407808"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342270"},{"key":"e_1_2_2_38_1","volume-title":"Accessed","year":"2023","unstructured":"Microsoft. Accessed in July, 2023. Azure Cosmos DB. https:\/\/learn.microsoft.com\/en-us\/azure\/cosmos-db\/consistency-levels."},{"key":"e_1_2_2_39_1","volume-title":"Accessed","author":"DB.","year":"2023","unstructured":"MongoDB. Accessed in July, 2023. Read Isolation, Consistency, and Recency. https:\/\/docs.mongodb.com\/manual\/core\/read-isolation-consistency-recency\/."},{"key":"e_1_2_2_40_1","volume-title":"Accessed","author":"SQL.","year":"2023","unstructured":"MySQL. Accessed in July, 2023. MySQL Cluster CGE. https:\/\/www.mysql.com\/products\/cluster\/."},{"key":"e_1_2_2_41_1","volume-title":"Accessed","year":"2023","unstructured":"Neo4j. Accessed in July, 2023. https:\/\/neo4j.com\/docs\/operations-manual\/current\/clustering\/introduction\/."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851170"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"},{"key":"e_1_2_2_46_1","volume-title":"PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication. In ICDCS","author":"Spirovska Kristina","year":"2019","unstructured":"Kristina Spirovska, Diego Didona, and Willy Zwaenepoel. 2019. PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication. In ICDCS 2019. IEEE, 304--316."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3026778"},{"key":"e_1_2_2_48_1","volume-title":"Welch","author":"Terry Douglas B.","year":"1994","unstructured":"Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike Spreitzer, Marvin Theimer, and Brent B. Welch. 1994. Session Guarantees for Weakly Consistent Replicated Data. In PDIS. IEEE Computer Society, 140--149."},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Alejandro Z. Tomsic Manuel Bravo and Marc Shapiro. 2018. Distributed transactional reads: the strong the quick the fresh & the impossible. In Middleware'18. ACM 120--133.","DOI":"10.1145\/3274808.3274818"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523221"},{"key":"e_1_2_2_51_1","volume-title":"An Integrated Experimental Environment for Distributed Systems and Networks","author":"White Brian","unstructured":"Brian White, Jay Lepreau, Leigh Stoller, Robert Ricci, Shashi Guruprasad, Mac Newbold, Mike Hibler, Chad Barb, and Abhijeet Joglekar. 2002. An Integrated Experimental Environment for Distributed Systems and Networks. In OSDI. USENIX Association, 255--270."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468521"},{"key":"e_1_2_2_53_1","volume-title":"SOSP","author":"Zhang Irene","year":"2015","unstructured":"Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. Building consistent transactions with inconsistent replication. In SOSP 2015. ACM, 263--278."},{"key":"e_1_2_2_54_1","volume-title":"OSDI'19","author":"Zhou Fang","year":"2018","unstructured":"Fang Zhou, Yifan Gan, Sixiang Ma, and Yang Wang. 2018. wPerf: Generic Off-CPU Analysis to Identify Bottleneck Waiting Events. In OSDI'19. USENIX Association, 527--543."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639264","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:12:09Z","timestamp":1755789129000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639264"],"URL":"https:\/\/doi.org\/10.1145\/3639264","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}