{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T05:13:50Z","timestamp":1747458830108},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>\n            We propose DSON, a space efficient \u03b4-based CRDT approach for distributed JSON document stores, enabling high availability at a global scale, while providing\n            <jats:bold>strong<\/jats:bold>\n            eventual consistency guarantees. We define the semantics of our CRDT based approach formally, and prove its correctness and convergence. Previous approaches optimize for collaborative document editing and store metadata proportional to the number of updates to a document, which is not acceptable for long lived document management. The metadata stored with our approach is bounded by\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>D<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of replicas,\n            <jats:italic>D<\/jats:italic>\n            is the number of document elements, and\n            <jats:italic>k<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            is the number of concurrent document updates. We also implement our approach[37] and demonstrate its space efficiency empirically. Experimental analysis shows that the metadata stored is typically significantly less than the worst case. This provides the basis for robust highly available distributed document stores with well defined semantics and safety guarantees, relieving application developers from the burden of conflict resolution.\n          <\/jats:p>","DOI":"10.14778\/3510397.3510403","type":"journal-article","created":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T22:23:10Z","timestamp":1652912590000},"page":"1053-1065","source":"Crossref","is-referenced-by-count":5,"title":["DSON"],"prefix":"10.14778","volume":"15","author":[{"given":"Arik","family":"Rinberg","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomer","family":"Solomon","sequence":"additional","affiliation":[{"name":"IBM, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roee","family":"Shlomo","sequence":"additional","affiliation":[{"name":"IBM, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Khazma","sequence":"additional","affiliation":[{"name":"IBM, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gal","family":"Lushi","sequence":"additional","affiliation":[{"name":"IBM, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Idit","family":"Keidar","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paula","family":"Ta-Shma","sequence":"additional","affiliation":[{"name":"IBM, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. Akka. https:\/\/akka.io\/.  2021. Akka. https:\/\/akka.io\/."},{"key":"e_1_2_1_2_1","unstructured":"2021. Automerge. https:\/\/github.com\/automerge\/automerge.  2021. Automerge. https:\/\/github.com\/automerge\/automerge."},{"key":"e_1_2_1_3_1","unstructured":"2021. Couchbase. https:\/\/www.couchbase.com\/.  2021. Couchbase. https:\/\/www.couchbase.com\/."},{"key":"e_1_2_1_4_1","unstructured":"2021. Couchbase Availability. https:\/\/docs.couchbase.com\/server\/5.5\/understanding-couchbase\/clusters-and-availability\/replication-architecture.html.  2021. Couchbase Availability. https:\/\/docs.couchbase.com\/server\/5.5\/understanding-couchbase\/clusters-and-availability\/replication-architecture.html."},{"key":"e_1_2_1_5_1","unstructured":"2021. CouchDB. https:\/\/couchdb.apache.org\/.  2021. CouchDB. https:\/\/couchdb.apache.org\/."},{"key":"e_1_2_1_6_1","unstructured":"2021. DynamoDB. https:\/\/aws.amazon.com\/dynamodb\/.  2021. DynamoDB. https:\/\/aws.amazon.com\/dynamodb\/."},{"key":"e_1_2_1_7_1","unstructured":"2021. IBM Cloudant on Transaction Engine Documentation. https:\/\/cloud.ibm.com\/docs\/Cloudant?topic=Cloudant-overview-te.  2021. IBM Cloudant on Transaction Engine Documentation. https:\/\/cloud.ibm.com\/docs\/Cloudant?topic=Cloudant-overview-te."},{"key":"e_1_2_1_8_1","unstructured":"2021. JavaScript Proxy. https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Proxy.  2021. JavaScript Proxy. https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Proxy."},{"key":"e_1_2_1_9_1","unstructured":"2021. JSON. https:\/\/www.json.org\/json-en.html.  2021. JSON. https:\/\/www.json.org\/json-en.html."},{"key":"e_1_2_1_10_1","unstructured":"2021. Peer-base\/JS-delta-crdts: Delta State-based CRDTs in Javascript. https:\/\/github.com\/peer-base\/js-delta-crdts  2021. Peer-base\/JS-delta-crdts: Delta State-based CRDTs in Javascript. https:\/\/github.com\/peer-base\/js-delta-crdts"},{"key":"e_1_2_1_11_1","unstructured":"2021. Riak. https:\/\/riak.com\/index.html.  2021. Riak. https:\/\/riak.com\/index.html."},{"key":"e_1_2_1_12_1","unstructured":"2021. Yjs. https:\/\/github.com\/yjs\/yjs.  2021. Yjs. https:\/\/github.com\/yjs\/yjs."},{"key":"e_1_2_1_13_1","unstructured":"2021. Yjs Forum: Map Metadata Overhead. https:\/\/discuss.yjs.dev\/t\/map-metadata-overhead\/492.  2021. Yjs Forum: Map Metadata Overhead. https:\/\/discuss.yjs.dev\/t\/map-metadata-overhead\/492."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26850-7_5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.08.003"},{"key":"e_1_2_1_16_1","volume-title":"CouchDB: The Definitive Guide","author":"Anderson J Chris","unstructured":"J Chris Anderson , Jan Lehnardt , and Noah Slater . 2010. CouchDB: The Definitive Guide , chapter 17: Conflict Management. \"O'Reilly Media, Inc. \". J Chris Anderson, Jan Lehnardt, and Noah Slater. 2010. CouchDB: The Definitive Guide, chapter 17: Conflict Management. \"O'Reilly Media, Inc.\"."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43352-2_11"},{"key":"e_1_2_1_18_1","first-page":"2","volume-title":"Ipfs-content addressed, versioned","author":"Benet Juan","year":"2014","unstructured":"Juan Benet . 2014. Ipfs-content addressed, versioned , p 2 p file system. arXiv preprint arXiv:1407.3561 ( 2014 ). Juan Benet. 2014. Ipfs-content addressed, versioned, p2p file system. arXiv preprint arXiv:1407.3561 (2014)."},{"key":"e_1_2_1_19_1","volume-title":"Semilattice structures","author":"Chajda Ivan","unstructured":"Ivan Chajda , Radom\u00edr Hala\u0161 , and Jan K\u00fchr . 2007. Semilattice structures . Vol. 30 . Heldermann Lemgo . Ivan Chajda, Radom\u00edr Hala\u0161, and Jan K\u00fchr. 2007. Semilattice structures. Vol. 30. Heldermann Lemgo."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00022"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380787.3393679"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2181796.2187821"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434770.3459730"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380787.3393677"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2697382"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Rusty Klophaus. 2010. Riak core: Building distributed applications without shared state. In ACM SIGPLAN Commercial Users of Functional Programming. 1--1.  Rusty Klophaus. 2010. Riak core: Building distributed applications without shared state. In ACM SIGPLAN Commercial Users of Functional Programming. 1--1.","DOI":"10.1145\/1900160.1900176"},{"key":"e_1_2_1_27_1","unstructured":"Leslie Lamport. 1978. Time clocks and the ordering of events in a distributed system. In Concurrency: the Works of Leslie Lamport. 179--196.  Leslie Lamport. 1978. Time clocks and the ordering of events in a distributed system. In Concurrency: the Works of Leslie Lamport. 179--196."},{"key":"e_1_2_1_28_1","volume-title":"Decentralized Kubernetes Federation Control Plane. In 2020 IEEE\/ACM 13th International Conference on Utility and Cloud Computing (UCC). IEEE, 354--359","author":"Larsson Lars","year":"2020","unstructured":"Lars Larsson , Harald Gustafsson , Cristian Klein , and Erik Elmroth . 2020 . Decentralized Kubernetes Federation Control Plane. In 2020 IEEE\/ACM 13th International Conference on Utility and Cloud Computing (UCC). IEEE, 354--359 . Lars Larsson, Harald Gustafsson, Cristian Klein, and Erik Elmroth. 2020. Decentralized Kubernetes Federation Control Plane. In 2020 IEEE\/ACM 13th International Conference on Utility and Cloud Computing (UCC). IEEE, 354--359."},{"key":"e_1_2_1_29_1","volume-title":"INRIA","author":"Letia M Mihai","year":"2009","unstructured":"M Mihai Letia , N Preguica , and M Shapiro . 2009. CRDTs: Consistency without concurrency control. RR-6956 , INRIA ( 2009 ). M Mihai Letia, N Preguica, and M Shapiro. 2009. CRDTs: Consistency without concurrency control. RR-6956, INRIA (2009)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494266.2494278"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2957276.2957310"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180875.1180916"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.20"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.20"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447865.3457971"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Arik Rinberg Tomer Solomon Roee Shlomo Guy Khazma and Gal Lushi. 2021. DSON - JSON CRDT Using Delta-Mutations. https:\/\/github.com\/crdt-ibm-research\/json-delta-crdt.  Arik Rinberg Tomer Solomon Roee Shlomo Guy Khazma and Gal Lushi. 2021. DSON - JSON CRDT Using Delta-Mutations. https:\/\/github.com\/crdt-ibm-research\/json-delta-crdt.","DOI":"10.1145\/3447865.3457971"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.12.006"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.12.006"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050613.2050642"},{"key":"e_1_2_1_41_1","unstructured":"solid IT. 2021. DB-Engines Ranking of Document Stores. https:\/\/db-engines.com\/en\/ranking\/document+store.  solid IT. 2021. DB-Engines Ranking of Document Stores. https:\/\/db-engines.com\/en\/ranking\/document+store."},{"key":"e_1_2_1_42_1","unstructured":"solid IT. 2021. DBMS popularity broken down by database model. https:\/\/db-engines.com\/en\/ranking_categories.  solid IT. 2021. DBMS popularity broken down by database model. https:\/\/db-engines.com\/en\/ranking_categories."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1994.331722"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.75"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3510397.3510403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:23:19Z","timestamp":1672219399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3510397.3510403"}},"subtitle":["JSON CRDT using delta-mutations for document stores"],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["10.14778\/3510397.3510403"],"URL":"https:\/\/doi.org\/10.14778\/3510397.3510403","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}