{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T15:24:25Z","timestamp":1787844265502,"version":"build-2784847793"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,30]],"date-time":"2017-11-30T00:00:00Z","timestamp":1512000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0963754, No. CNS-1217597, No. CNS-1318396, No. CNS-1420703, No. CNS-1518702, and No. CNS-1615102"],"award-info":[{"award-number":["CNS-0963754, No. CNS-1217597, No. CNS-1318396, No. CNS-1420703, No. CNS-1518702, and No. CNS-1615102"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Google and VMware"},{"name":"NSF GRFP and IBM Ph.D. fellowships"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>Application programmers increasingly prefer distributed storage systems with strong consistency and distributed transactions (e.g., Google\u2019s Spanner) for their strong guarantees and ease of use. Unfortunately, existing transactional storage systems are expensive to use\u2014in part, because they require costly replication protocols, like Paxos, for fault tolerance. In this article, we present a new approach that makes transactional storage systems more affordable: We eliminate consistency from the replication protocol, while still providing distributed transactions with strong consistency to applications.<\/jats:p>\n                  <jats:p>\n                    We present the Transactional Application Protocol for Inconsistent Replication (TAPIR), the first transaction protocol to use a novel replication protocol, called\n                    <jats:italic>inconsistent replication<\/jats:italic>\n                    , that provides fault tolerance without consistency. By enforcing strong consistency only in the transaction protocol, TAPIR can commit transactions in a single round-trip and order distributed transactions without centralized coordination. We demonstrate the use of TAPIR in a transactional key-value store,\n                    <jats:sc>TAPIR-KV<\/jats:sc>\n                    . Compared to conventional systems,\n                    <jats:sc>TAPIR-KV<\/jats:sc>\n                    provides better latency\n                    <jats:italic>and<\/jats:italic>\n                    better throughput.\n                  <\/jats:p>","DOI":"10.1145\/3269981","type":"journal-article","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T08:17:16Z","timestamp":1545034636000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Building Consistent Transactions with Inconsistent Replication"],"prefix":"10.1145","volume":"35","author":[{"given":"Irene","family":"Zhang","sequence":"first","affiliation":[{"name":"Microsoft Research, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Naveen Kr.","family":"Sharma","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adriana","family":"Szekeres","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arvind","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan R. K.","family":"Ports","sequence":"additional","affiliation":[{"name":"Microsoft Research, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223787"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294278"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Conference on Very Large Databases (VLDB\u201914)","author":"Bailis Peter","year":"2014","unstructured":"Peter Bailis , Aaron Davidson , Alan Fekete , Ali Ghodsi , Joseph M. Hellerstein , and Ion Stoica . 2014 . Highly available transactions: Virtues and limitations . In Proceedings of the Conference on Very Large Databases (VLDB\u201914) . Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2014. Highly available transactions: Virtues and limitations. In Proceedings of the Conference on Very Large Databases (VLDB\u201914)."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201911)","author":"Baker Jason","year":"2011","unstructured":"Jason Baker , Chris Bond , James Corbett , J. J. Furman , Andrey Khorlin , James Larson , Jean-Michel L\u00e9on , Yawei Li , Alexander Lloyd , and Vadim Yushprakh . 2011 . Megastore: Providing scalable, highly available storage for interactive services . In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201911) . Jason Baker, Chris Bond, James Corbett, J. J. Furman, Andrey Khorlin, James Larson, Jean-Michel L\u00e9on, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing scalable, highly available storage for interactive services. In Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201911)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522732"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_1_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 . Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison Wesley."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/41457.37515"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Burrows Mike","year":"2006","unstructured":"Mike Burrows . 2006 . The Chubby lock service for loosely coupled distributed systems . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906) . Mike Burrows. 2006. The Chubby lock service for loosely coupled distributed systems. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2901318.2901349"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522712"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)","author":"James","unstructured":"James C. Corbett et al. 2012. Spanner: Google\u2019s globally distributed database . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912) . James C. Corbett et al. 2012. Spanner: Google\u2019s globally distributed database. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201912)","author":"Cowling James","year":"2012","unstructured":"James Cowling and Barbara Liskov . 2012 . Granola: Low-overhead distributed transaction coordination . In Proceedings of the USENIX Annual Technical Conference (ATC\u201912) . James Cowling and Barbara Liskov. 2012. Granola: Low-overhead distributed transaction coordination. In Proceedings of the USENIX Annual Technical Conference (ATC\u201912)."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Cowling James","year":"2006","unstructured":"James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , and Liuba Shrira . 2006 . HQ replication: A hybrid quorum protocol for Byzantine fault tolerance . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906) . James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. 2006. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2014.6818330"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914)","author":"Dragojevi\u0107 Aleksandar","year":"2014","unstructured":"Aleksandar Dragojevi\u0107 , Dushyanth Narayanan , Orion Hodson , and Miguel Castro . 2014 . FaRM: Fast remote memory . In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914) . USENIX. Aleksandar Dragojevi\u0107, Dushyanth Narayanan, Orion Hodson, and Miguel Castro. 2014. FaRM: Fast remote memory. In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914). USENIX."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2013.26"},{"key":"e_1_2_1_23_1","volume-title":"Warp: Multi-Key Transactions for Key-Value Stores. Technical Report. Cornell.","author":"Escriva Robert","year":"2013","unstructured":"Robert Escriva , Bernard Wong , and Emin Gun Sirer . 2013 . Warp: Multi-Key Transactions for Key-Value Stores. Technical Report. Cornell. Robert Escriva, Bernard Wong, and Emin Gun Sirer. 2013. Warp: Multi-Key Transactions for Key-Value Stores. Technical Report. Cornell."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800215.806583"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132867"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201910)","author":"Hunt Patrick","year":"2010","unstructured":"Patrick Hunt , Mahadev Konar , Flavio Paiva Junqueira , and Benjamin Reed . 2010 . ZooKeeper: Wait-free coordination for internet-scale systems . In Proceedings of the USENIX Annual Technical Conference (ATC\u201910) . Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin Reed. 2010. ZooKeeper: Wait-free coordination for internet-scale systems. In Proceedings of the USENIX Annual Technical Conference (ATC\u201910)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1323140.1323158"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258660"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465363"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138877"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177726"},{"key":"e_1_2_1_35_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 32 , 4 (Dec. 2001), 51--58. Leslie Lamport. 2001. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 51--58.","journal-title":"ACM SIGACT News"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0005-x"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0155-x"},{"key":"e_1_2_1_39_1","unstructured":"Costin Leau. 2013. Spring Data Redis--Retwis-J. Retrieved from http:\/\/docs.spring.io\/spring-data\/data-keyvalue\/examples\/retwisj\/current\/.  Costin Leau. 2013. Spring Data Redis--Retwis-J. Retrieved from http:\/\/docs.spring.io\/spring-data\/data-keyvalue\/examples\/retwisj\/current\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132751"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916)","author":"Li Jialin","unstructured":"Jialin Li , Ellis Michael , Adriana Szekeres , Naveen Kr. Sharma , and Dan R. K. Ports . 2016. Just say no to Paxos overhead: Replacing consensus with network ordering . In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916) . USENIX. Jialin Li, Ellis Michael, Adriana Szekeres, Naveen Kr. Sharma, and Dan R. K. Ports. 2016. Just say no to Paxos overhead: Replacing consensus with network ordering. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916). USENIX."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646156.679840"},{"key":"e_1_2_1_43_1","unstructured":"Barbara Liskov and James Cowling. 2012. Viewstamped replication revisited. Technical report MIT-CSAIL-TR-2012-021. MIT.  Barbara Liskov and James Cowling. 2012. Viewstamped replication revisited. Technical report MIT-CSAIL-TR-2012-021. MIT."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536366"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050050"},{"key":"e_1_2_1_47_1","unstructured":"MongoDB. 2013. MongoDB: A open-source document database. Retrieved from http:\/\/www.mongodb.org\/.  MongoDB. 2013. MongoDB: A open-source document database. Retrieved from http:\/\/www.mongodb.org\/."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201914)","author":"Mu Shuai","year":"2014","unstructured":"Shuai Mu , Yang Cui , Yang Zhang , Wyatt Lloyd , and Jinyang Li . 2014 . Extracting more concurrency from distributed transactions . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201914) . Shuai Mu, Yang Cui, Yang Zhang, Wyatt Lloyd, and Jinyang Li. 2014. Extracting more concurrency from distributed transactions. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201914)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026917"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/62546.62549"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201915)","author":"Ports Dan R. K.","year":"2015","unstructured":"Dan R. K. Ports , Jialin Li , Vincent Liu , Naveen Kr. Sharma , and Arvind Krishnamurthy . 2015 . Designing distributed systems using approximate synchrony in data center networks . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201915) . Dan R. K. Ports, Jialin Li, Vincent Liu, Naveen Kr. Sharma, and Arvind Krishnamurthy. 2015. Designing distributed systems using approximate synchrony in data center networks. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201915)."},{"key":"e_1_2_1_53_1","volume-title":"Redis: Open Source Data Structure Server.","year":"2013","unstructured":"Redis. 2013 . Redis: Open Source Data Structure Server. Retrieved from http:\/\/redis.io\/. Redis. 2013. Redis: Open Source Data Structure Server. Retrieved from http:\/\/redis.io\/."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057977.1057980"},{"key":"e_1_2_1_55_1","volume-title":"WAIT: Synchronous replication for Redis.","author":"Sanfilippo Salvatore","year":"2013","unstructured":"Salvatore Sanfilippo . 2013 . WAIT: Synchronous replication for Redis. Retrieved from http:\/\/antirez.com\/news\/66. Salvatore Sanfilippo. 2013. WAIT: Synchronous replication for Redis. Retrieved from http:\/\/antirez.com\/news\/66."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_30"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/224056.224070"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320076"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815419"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815404"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522729"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3269981","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3269981","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3269981","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:57:21Z","timestamp":1750193841000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3269981"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,30]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3269981"],"URL":"https:\/\/doi.org\/10.1145\/3269981","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,30]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}