{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:02:43Z","timestamp":1757610163866,"version":"3.44.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p>Many linearizable local read algorithms have been proposed to minimize the read latency of strongly consistent distributed databases deployed in geo-distributed networks. These algorithms do so by enabling reads to be performed immediately against any process' copy of the database in the best case. However, as our analysis shows, worst-case read latency at every process with all existing algorithms is at least the network's relative diameter in terms of the maximum message delay minus a known lower bound on message delay between any two processes. We then show that by leveraging the asymmetric message delays of geo-distributed networks, worst-case read latency can be below the network's relative diameter at processes close to the leader or the network's center by presenting two new linearizable local read algorithms. Our experimental evaluation shows that these new algorithms reduce worst-case read latency by up to 50x compared to existing ones.<\/jats:p>","DOI":"10.14778\/3742728.3742738","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:32:53Z","timestamp":1756906373000},"page":"2427-2439","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymmetric Linearizable Local Reads"],"prefix":"10.14778","volume":"18","author":[{"given":"Myles","family":"Thiessen","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]},{"given":"Guy","family":"Khazma","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]},{"given":"Sam","family":"Toueg","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]},{"given":"Eyal","family":"de Lara","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. https:\/\/aws.amazon.com\/. Accessed: 2025-05-19."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. http:\/\/rocksdb.org.. Accessed: 2025-05-19."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. https:\/\/grpc.io\/. Accessed: 2025-05-19."},{"key":"e_1_2_1_4_1","volume-title":"5th Annual Linux Expo. 153\u2013164","author":"Almesberger Werner","year":"1999","unstructured":"Werner Almesberger. 1999. Linux network traffic control-implementation overview. In 5th Annual Linux Expo. 153\u2013164."},{"key":"e_1_2_1_5_1","first-page":"223","article-title":"Megastore: Providing scalable, highly available storage for interactive services","volume":"11","author":"Baker Jason","year":"2011","unstructured":"Jason Baker, Chris Bond, James C Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing scalable, highly available storage for interactive services.. In CIDR, Vol. 11. 223\u2013234.","journal-title":"CIDR"},{"key":"e_1_2_1_6_1","volume-title":"Parameterized algorithm for replicated objects with local reads. arXiv preprint arXiv:2204.01228","author":"Bi Changyu","year":"2022","unstructured":"Changyu Bi, Vassos Hadzilacos, and Sam Toueg. 2022. Parameterized algorithm for replicated objects with local reads. arXiv preprint arXiv:2204.01228 (2022)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0020-0190(01)00151-X","article-title":"Closed form bounds for clock synchronization under simple uncertainty assumptions","volume":"80","author":"Biaz Sa\u00e2d","year":"2001","unstructured":"Sa\u00e2d Biaz and Jennifer L Welch. 2001. Closed form bounds for clock synchronization under simple uncertainty assumptions. Inform. Process. Lett. 80, 3 (2001), 151\u2013157.","journal-title":"Inform. Process. Lett."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 398\u2013407","author":"Chandra Tushar D","year":"2007","unstructured":"Tushar D Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 398\u2013407."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. 325\u2013334","author":"Chandra Tushar D","year":"2016","unstructured":"Tushar D Chandra, Vassos Hadzilacos, and Sam Toueg. 2016. An algorithm for replicated objects with efficient reads. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. 325\u2013334."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 1st ACM symposium on Cloud computing. 143\u2013154","author":"Cooper Brian F","year":"2010","unstructured":"Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing. 143\u2013154."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2491245","article-title":"Spanner: Google's globally distributed database","volume":"31","author":"Corbett James C","year":"2013","unstructured":"James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, et al. 2013. Spanner: Google's globally distributed database. ACM Transactions on Computer Systems (TOCS) 31, 3 (2013), 1\u201322.","journal-title":"ACM Transactions on Computer Systems (TOCS)"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1109\/71.774912","article-title":"The timed asynchronous distributed system model","volume":"10","author":"Cristian Flaviu","year":"1999","unstructured":"Flaviu Cristian and Christof Fetzer. 1999. The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed systems 10, 6 (1999), 642\u2013657.","journal-title":"IEEE Transactions on Parallel and Distributed systems"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Fifteenth European Conference on Computer Systems. 1\u201315","author":"Enes Vitor","year":"2020","unstructured":"Vitor Enes, Carlos Baquero, Tuanir Fran\u00e7a Rezende, Alexey Gotsman, Matthieu Perrin, and Pierre Sutra. 2020. State-machine replication for planet-scale systems. In Proceedings of the Fifteenth European Conference on Computer Systems. 1\u201315."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"629","DOI":"10.14778\/3574245.3574250","article-title":"Nezha: Deployable and High-Performance Consensus Using Synchronized Clocks","volume":"16","author":"Geng Jinkun","year":"2022","unstructured":"Jinkun Geng, Anirudh Sivaraman, Balaji Prabhakar, and Mendel Rosenblum. 2022. Nezha: Deployable and High-Performance Consensus Using Synchronized Clocks. Proceedings of the VLDB Endowment 16, 4 (2022), 629\u2013642.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/74851.74870","article-title":"Leases: An efficient fault-tolerant mechanism for distributed file cache consistency","volume":"23","author":"Gray Cary","year":"1989","unstructured":"Cary Gray and David Cheriton. 1989. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. ACM SIGOPS Operating Systems Review 23, 5 (1989), 202\u2013210.","journal-title":"ACM SIGOPS Operating Systems Review"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM symposium on cloud computing. 1\u201314","author":"Gunawi Haryadi S","year":"2014","unstructured":"Haryadi S Gunawi, Mingzhe Hao, Tanakorn Leesatapornwongsa, Tiratat Patanaanake, Thanh Do, Jeffry Adityatama, Kurnia J Eliazar, Agung Laksono, Jeffrey F Lukman, Vincentius Martin, et al. 2014. What bugs live in the cloud? a study of 3000+ issues in cloud systems. In Proceedings of the ACM symposium on cloud computing. 1\u201314."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","article-title":"Linearizability: A correctness condition for concurrent objects","volume":"12","author":"Herlihy Maurice P","year":"1990","unstructured":"Maurice P Herlihy and Jeannette M Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463\u2013492.","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"},{"key":"e_1_2_1_18_1","volume-title":"Abishek Bangalore Muralikrishna, and Aleksey Charapko","author":"Hilyard Owen","year":"2023","unstructured":"Owen Hilyard, Bocheng Cui, Marielle Webster, Abishek Bangalore Muralikrishna, and Aleksey Charapko. 2023. Cloudy Forecast: How Predictable is Communication Latency in the Cloud? arXiv preprint arXiv:2309.13169 (2023)."},{"key":"e_1_2_1_19_1","volume-title":"2020 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, 180\u2013191","author":"Siavash Katebzadeh MR","year":"2020","unstructured":"MR Siavash Katebzadeh, Paolo Costa, and Boris Grot. 2020. Evaluation of an infiniband switch: Choose latency or bandwidth, but not both. In 2020 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, 180\u2013191."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 201\u2013217","author":"Katsarakis Antonios","year":"2020","unstructured":"Antonios Katsarakis, Vasilis Gavrielatos, MR Siavash Katebzadeh, Arpit Joshi, Aleksandar Dragojevic, Boris Grot, and Vijay Nagarajan. 2020. Hermes: A fast, fault-tolerant and linearizable replication protocol. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 201\u2013217."},{"key":"e_1_2_1_21_1","first-page":"4","article-title":"Paxos made simple","volume":"32","author":"Lamport Leslie","year":"2001","unstructured":"Leslie Lamport. 2001. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001), 51\u201358.","journal-title":"ACM SIGACT News (Distributed Computing Column)"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the twenty-first international conference on architectural support for programming languages and operating systems. 517\u2013530","author":"Leesatapornwongsa Tanakorn","year":"2016","unstructured":"Tanakorn Leesatapornwongsa, Jeffrey F Lukman, Shan Lu, and Haryadi S Gunawi. 2016. TaxDC: A taxonomy of non-deterministic concurrency bugs in datacenter distributed systems. In Proceedings of the twenty-first international conference on architectural support for programming languages and operating systems. 517\u2013530."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1667053.1667057","article-title":"Tight bounds for clock synchronization","volume":"57","author":"Lenzen Christoph","year":"2010","unstructured":"Christoph Lenzen, Thomas Locher, and Roger Wattenhofer. 2010. Tight bounds for clock synchronization. Journal of the ACM (JACM) 57, 2 (2010), 1\u201342.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_2_1_24_1","volume-title":"14th USENIX symposium on operating systems design and implementation (OSDI 20)","author":"Li Yuliang","year":"2020","unstructured":"Yuliang Li, Gautam Kumar, Hema Hariharan, Hassan Wassel, Peter Hochschild, Dave Platt, Simon Sabato, Minlan Yu, Nandita Dukkipati, Prashant Chandra, et al. 2020. Sundial: Fault-tolerant clock synchronization for datacenters. In 14th USENIX symposium on operating systems design and implementation (OSDI 20). 1171\u20131186."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"David L Mills. 1985. Network time protocol (NTP). Technical Report.","DOI":"10.17487\/rfc0958"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the ACM Symposium on Cloud Computing. 1\u201313","author":"Moraru Iulian","year":"2014","unstructured":"Iulian Moraru, David G Andersen, and Michael Kaminsky. 2014. Paxos quorum leases: Fast reads without sacrificing writes. In Proceedings of the ACM Symposium on Cloud Computing. 1\u201313."},{"key":"e_1_2_1_27_1","unstructured":"Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In 2014 USENIX annual technical conference (USENIX ATC 14). 305\u2013319."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1145\/98163.98167","article-title":"Implementing fault-tolerant services using the state machine approach: A tutorial","volume":"22","author":"Schneider Fred B","year":"1990","unstructured":"Fred B Schneider. 1990. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR) 22, 4 (1990), 299\u2013319.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2022 International Conference on Management of Data. 2312\u20132325","author":"VanBenschoten Nathan","year":"2022","unstructured":"Nathan VanBenschoten, Arul Ajmani, Marcus Gartner, Andrei Matei, Aayush Shah, Irfan Sharif, Alexander Shraer, Adam Storm, Rebecca Taft, Oliver Tan, et al. 2022. Enabling the next generation of multi-region applications with cockroachdb. In Proceedings of the 2022 International Conference on Management of Data. 2312\u20132325."},{"key":"e_1_2_1_30_1","first-page":"2203","article-title":"Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection","volume":"13","author":"Zhu Hang","year":"2019","unstructured":"Hang Zhu, Zhihao Bai, Jialin Li, Ellis Michael, Dan R. K. Ports, Ion Stoica, and Xin Jin. 2019. Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection. Proceedings of the VLDB Endowment 13, 3 (2019), 2203\u20132215.","journal-title":"Proceedings of the VLDB Endowment"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3742728.3742738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:36:39Z","timestamp":1756906599000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3742728.3742738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":30,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.14778\/3742728.3742738"],"URL":"https:\/\/doi.org\/10.14778\/3742728.3742738","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}