{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T23:44:16Z","timestamp":1767829456035,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Multi-master architecture is desirable for cloud databases in supporting large-scale transaction processing. To enable concurrent transaction execution on multiple computing nodes, we need an efficient transaction commit protocol on the storage layer that ensures ACID as well as consensus among replicas. A leader-based protocol is easy to implement. However, it faces the single-node bottleneck and suffers from high transaction latency in cross-region deployment. While a leaderless protocol can achieve a higher degree of parallelism, it is inefficient in resolving conflicts.<\/jats:p>\n          <jats:p>This paper proposes the semi-leader protocol, which is a new type of transaction commit protocol for multi-master transaction processing. In a nutshell, the semi-leader protocol is a hybrid protocol that offers separate commit paths for conflicting transactions and non-conflicting transactions. A centralized node, known as the sequencer, is employed to perform precise conflict resolution for conflicting transactions, while non-conflicting transactions can be committed timely in a decentralized manner. Based on the semi-leader protocol, we designed Starry, a multi-master transaction processing mechanism. Experimental results demonstrate that Starry is 1.4\u00d7 and 4.21\u00d7 as performant as the leaderless and leader-based protocols respectively in throughput. When dealing with high-contention workloads, Starry can significantly reduce the abort rates.<\/jats:p>","DOI":"10.14778\/3561261.3561268","type":"journal-article","created":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T15:32:50Z","timestamp":1668612770000},"page":"77-89","source":"Crossref","is-referenced-by-count":6,"title":["Starry"],"prefix":"10.14778","volume":"16","author":[{"given":"Zihao","family":"Zhang","sequence":"first","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huiqi","family":"Hu","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiang","family":"Wang","sequence":"additional","affiliation":[{"name":"Huawei Co., Ltd."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2018. PolarDB. https:\/\/www.alibabacloud.com\/product\/polardb.  2018. PolarDB. https:\/\/www.alibabacloud.com\/product\/polardb."},{"key":"e_1_2_1_2_1","unstructured":"2018. Presto. https:\/\/prestodb.io\/.  2018. Presto. https:\/\/prestodb.io\/."},{"key":"e_1_2_1_3_1","unstructured":"2020. Amazon Redshift. https:\/\/aws.amazon.com\/cn\/redshift\/.  2020. Amazon Redshift. https:\/\/aws.amazon.com\/cn\/redshift\/."},{"key":"e_1_2_1_4_1","unstructured":"2020. Aurora multi-master. https:\/\/docs.aws.amazon.com\/AmazonRDS\/latest\/AuroraUserGuide\/aurora-multi-master.html.  2020. Aurora multi-master. https:\/\/docs.aws.amazon.com\/AmazonRDS\/latest\/AuroraUserGuide\/aurora-multi-master.html."},{"key":"e_1_2_1_5_1","unstructured":"2022. IBM multi-master. https:\/\/www.ibm.com\/docs\/en\/sgklm\/4.1?topic=redundancy-configuring-multi-master-cluster.  2022. IBM multi-master. https:\/\/www.ibm.com\/docs\/en\/sgklm\/4.1?topic=redundancy-configuring-multi-master-cluster."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/32204.32220"},{"key":"e_1_2_1_7_1","unstructured":"Ozalp Babaoglu and Sam Toueg. 1993. Understanding Non-Blocking Atomic Commitment. In Distributed systems.  Ozalp Babaoglu and Sam Toueg. 1993. Understanding Non-Blocking Atomic Commitment. In Distributed systems."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Second International Symposium on Distributed Data Bases","author":"Bayer Rudolf","year":"1982","unstructured":"Rudolf Bayer , Klaus Elhardt , Johannes Heigert , and Angelika Reiser . 1982. Dynamic Timestamp Allocation for Transactions in Database Systems . In Proceedings of the Second International Symposium on Distributed Data Bases , Berlin, F.R.G. , September 1--3, 1982 . North-Holland Publishing Company , 9--20. Rudolf Bayer, Klaus Elhardt, Johannes Heigert, and Angelika Reiser. 1982. Dynamic Timestamp Allocation for Transactions in Database Systems. In Proceedings of the Second International Symposium on Distributed Data Bases, Berlin, F.R.G., September 1--3, 1982. North-Holland Publishing Company, 9--20."},{"key":"e_1_2_1_9_1","unstructured":"Wei Cao Yang Liu Zhushi Cheng Ning Zheng Wei Li Wenjie Wu Linqiang Ouyang Peng Wang Yijing Wang Ray Kuan Zhenjun Liu Feng Zhu and Tong Zhang. 2020. POLARDB Meets Computational Storage: Efficiently Support Analytical Workloads in Cloud-Native Relational Database. In FAST. 29--41.  Wei Cao Yang Liu Zhushi Cheng Ning Zheng Wei Li Wenjie Wu Linqiang Ouyang Peng Wang Yijing Wang Ray Kuan Zhenjun Liu Feng Zhu and Tong Zhang. 2020. POLARDB Meets Computational Storage: Efficiently Support Analytical Workloads in Cloud-Native Relational Database. In FAST. 29--41."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Wei Cao Yingqiang Zhang Xinjun Yang Feifei Li Sheng Wang Qingda Hu Xuntao Cheng Zongzhi Chen Zhenjun Liu Jing Fang Bo Wang Yuhui Wang Haiqing Sun Ze Yang Zhushi Cheng Sen Chen Jian Wu Wei Hu Jianwei Zhao Yusong Gao Songlu Cai Yunyang Zhang and Jiawang Tong. 2021. PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers. In SIGMOD. 2477--2489.  Wei Cao Yingqiang Zhang Xinjun Yang Feifei Li Sheng Wang Qingda Hu Xuntao Cheng Zongzhi Chen Zhenjun Liu Jing Fang Bo Wang Yuhui Wang Haiqing Sun Ze Yang Zhushi Cheng Sen Chen Jian Wu Wei Hu Jianwei Zhao Yusong Gao Songlu Cai Yunyang Zhang and Jiawang Tong. 2021. PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers. In SIGMOD. 2477--2489.","DOI":"10.1145\/3448016.3457560"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Tushar Deepak Chandra Robert Griesemer and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In PODC. 398--407.  Tushar Deepak Chandra Robert Griesemer and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In PODC. 398--407.","DOI":"10.1145\/1281100.1281103"},{"key":"e_1_2_1_12_1","volume-title":"Spanner: Google's Globally-Distributed Database. In OSDI. 251--264.","author":"Corbett James C.","year":"2012","unstructured":"James C. Corbett , Jeffrey Dean , Michael Epstein , Andrew Fikes , Christopher Frost , J. J. Furman , Sanjay Ghemawat , Andrey Gubarev , Christopher Heiser , Peter Hochschild , Wilson C. Hsieh , Sebastian Kanthak , Eugene Kogan , Hongyi Li , Alexander Lloyd , Sergey Melnik , David Mwaura , David Nagle , Sean Quinlan , Rajesh Rao , Lindsay Rolig , Yasushi Saito , Michal Szymaniak , Christopher Taylor , Ruth Wang , and Dale Woodford . 2012 . Spanner: Google's Globally-Distributed Database. In OSDI. 251--264. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson C. Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2012. Spanner: Google's Globally-Distributed Database. In OSDI. 251--264."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Beno\u00eet Dageville Thierry Cruanes Marcin Zukowski Vadim Antonov Artin Avanes Jon Bock Jonathan Claybaugh Daniel Engovatov Martin Hentschel Jiansheng Huang Allison W. Lee Ashish Motivala Abdul Q. Munir Steven Pelley Peter Povinec Greg Rahn Spyridon Triantafyllis and Philipp Unterbrunner. 2016. The Snowflake Elastic Data Warehouse. In SIGMOD. 215--226.  Beno\u00eet Dageville Thierry Cruanes Marcin Zukowski Vadim Antonov Artin Avanes Jon Bock Jonathan Claybaugh Daniel Engovatov Martin Hentschel Jiansheng Huang Allison W. Lee Ashish Motivala Abdul Q. Munir Steven Pelley Peter Povinec Greg Rahn Spyridon Triantafyllis and Philipp Unterbrunner. 2016. The Snowflake Elastic Data Warehouse. In SIGMOD. 215--226.","DOI":"10.1145\/2882903.2903741"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282502"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132867"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Stavros Harizopoulos Daniel J. Abadi Samuel Madden and Michael Stonebraker. 2008. OLTP through the looking glass and what we found there. In SIGMOD. 981--992.  Stavros Harizopoulos Daniel J. Abadi Samuel Madden and Michael Stonebraker. 2008. OLTP through the looking glass and what we found there. In SIGMOD. 981--992.","DOI":"10.1145\/1376616.1376713"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_19_1","volume-title":"Fekete","author":"Kraska Tim","year":"2013","unstructured":"Tim Kraska , Gene Pang , Michael J. Franklin , Samuel Madden , and Alan D . Fekete . 2013 . MDCC: multi-data center consistency. In EuroSys . 113--126. Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan D. Fekete. 2013. MDCC: multi-data center consistency. In EuroSys. 113--126."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_21_1","volume-title":"Cache Fusion: Extending Shared-Disk Clusters with Shared Caches. In VLDB. 683--686.","author":"Lahiri Tirthankar","year":"2001","unstructured":"Tirthankar Lahiri , Vinay Srihari , Wilson Chan , N. MacNaughton , and Sashikanth Chandrasekaran . 2001 . Cache Fusion: Extending Shared-Disk Clusters with Shared Caches. In VLDB. 683--686. Tirthankar Lahiri, Vinay Srihari, Wilson Chan, N. MacNaughton, and Sashikanth Chandrasekaran. 2001. Cache Fusion: Extending Shared-Disk Clusters with Shared Caches. In VLDB. 683--686."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_24_1","unstructured":"Leslie Lamport. 2005. Generalized consensus and Paxos. (2005).  Leslie Lamport. 2005. Generalized consensus and Paxos. (2005)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0005-x"},{"key":"e_1_2_1_26_1","unstructured":"Haonan Lu Christopher Hodsdon Khiem Ngo Shuai Mu and Wyatt Lloyd. 2016. The SNOW Theorem and Latency-Optimal Read-Only Transactions. In OSDI. 135--150.  Haonan Lu Christopher Hodsdon Khiem Ngo Shuai Mu and Wyatt Lloyd. 2016. The SNOW Theorem and Latency-Optimal Read-Only Transactions. In OSDI. 135--150."},{"key":"e_1_2_1_27_1","unstructured":"Haonan Lu Siddhartha Sen and Wyatt Lloyd. 2020. Performance-Optimal Read-Only Transactions. In OSDI. 333--349.  Haonan Lu Siddhartha Sen and Wyatt Lloyd. 2020. Performance-Optimal Read-Only Transactions. In OSDI. 333--349."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Iulian Moraru David G. Andersen and Michael Kaminsky. 2013. There is more consensus in Egalitarian parliaments. In SOSP. 358--372.  Iulian Moraru David G. Andersen and Michael Kaminsky. 2013. There is more consensus in Egalitarian parliaments. In SOSP. 358--372.","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_29_1","unstructured":"Shuai Mu Yang Cui Yang Zhang Wyatt Lloyd and Jinyang Li. 2014. Extracting More Concurrency from Distributed Transactions. In OSDI. 479--494.  Shuai Mu Yang Cui Yang Zhang Wyatt Lloyd and Jinyang Li. 2014. Extracting More Concurrency from Distributed Transactions. In OSDI. 479--494."},{"key":"e_1_2_1_30_1","unstructured":"Shuai Mu Lamont Nelson Wyatt Lloyd and Jinyang Li. 2016. Consolidating Concurrency Control and Consensus for Commits under Conflicts. In OSDI. 517--532.  Shuai Mu Lamont Nelson Wyatt Lloyd and Jinyang Li. 2016. Consolidating Concurrency Control and Consensus for Commits under Conflicts. In OSDI. 517--532."},{"key":"e_1_2_1_31_1","volume-title":"Ousterhout","author":"Ongaro Diego","year":"2014","unstructured":"Diego Ongaro and John K . Ousterhout . 2014 . In Search of an Understandable Consensus Algorithm. In ATC. 305--319. Diego Ongaro and John K. Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In ATC. 305--319."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582339"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Rebecca Taft Irfan Sharif Andrei Matei Nathan VanBenschoten Jordan Lewis Tobias Grieger Kai Niemi Andy Woods Anne Birzin Raphael Poss Paul Bardea Amruta Ranade Ben Darnell Bram Gruneir Justin Jaffray Lucy Zhang and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In SIGMOD. 1493--1509.  Rebecca Taft Irfan Sharif Andrei Matei Nathan VanBenschoten Jordan Lewis Tobias Grieger Kai Niemi Andy Woods Anne Birzin Raphael Poss Paul Bardea Amruta Ranade Ben Darnell Bram Gruneir Justin Jaffray Lucy Zhang and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In SIGMOD. 1493--1509.","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320076"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196937"},{"key":"e_1_2_1_38_1","volume-title":"Bernard Wong, Kenneth Salem, and Tim Brecht.","author":"Yan Xinan","year":"2018","unstructured":"Xinan Yan , Linguan Yang , Hongbo Zhang , Xiayue Charles Lin , Bernard Wong, Kenneth Salem, and Tim Brecht. 2018 . Carousel : Low-Latency Transaction Processing for Globally-Distributed Data. In SIGMOD. 231--243. Xinan Yan, Linguan Yang, Hongbo Zhang, Xiayue Charles Lin, Bernard Wong, Kenneth Salem, and Tim Brecht. 2018. Carousel: Low-Latency Transaction Processing for Globally-Distributed Data. In SIGMOD. 231--243."},{"key":"e_1_2_1_39_1","volume-title":"Ports","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. 263--278. Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. Building consistent transactions with inconsistent replication. In SOSP. 263--278."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3561261.3561268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:21:23Z","timestamp":1672219283000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3561261.3561268"}},"subtitle":["multi-master transaction processing on semi-leader architecture"],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.14778\/3561261.3561268"],"URL":"https:\/\/doi.org\/10.14778\/3561261.3561268","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}