<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Ricardo Gonçalves</style></author><author><style face="normal" font="default" size="100%">Paulo Sérgio Almeida</style></author><author><style face="normal" font="default" size="100%">Carlos Baquero Moreno</style></author><author><style face="normal" font="default" size="100%">Vitor Fonte</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">DottedDB: Anti-Entropy without Merkle Trees, Deletes without Tombstones</style></title><secondary-title><style face="normal" font="default" size="100%">36th IEEE International Symposium on Reliable Distributed Systems </style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">SRDS 2017</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2017</style></year><pub-dates><date><style  face="normal" font="default" size="100%">28 September</style></date></pub-dates></dates><urls><related-urls><url><style face="normal" font="default" size="100%">https://haslab.uminho.pt/sites/default/files/tome/files/dotteddb_srds.pdf</style></url></related-urls></urls><publisher><style face="normal" font="default" size="100%">IEEE</style></publisher><pub-location><style face="normal" font="default" size="100%">Hong Kong, China</style></pub-location><abstract><style face="normal" font="default" size="100%">&lt;p&gt;To achieve high availability in the face of network partitions, many distributed databases adopt eventual consistency, allow temporary conflicts due to concurrent writes, and use some form of per-key logical clock to detect and resolve such conflicts. Furthermore, nodes synchronize periodically to ensure replica convergence in a process called anti-entropy, normally using Merkle Trees. We present the design of DottedDB, a Dynamo-like key-value store, which uses a novel node-wide logical clock framework, overcoming three fundamental limitations of the state of the art: (1) minimize the metadata per key necessary to track causality, avoiding its growth even in the face of node churn; (2) correctly and durably delete keys, with no need for tombstones; (3) offer a lightweight anti-entropy mechanism to converge replicated data, avoiding the need for Merkle Trees. We evaluate DottedDB against MerkleDB, an otherwise identical database, but using per-key logical clocks and Merkle Trees for anti-entropy, to precisely measure the impact of the novel approach. Results show that: causality metadata per object always converges rapidly to only one id-counter pair; distributed deletes are correctly achieved without global coordination and with constant metadata; divergent nodes are synchronized faster, with less memory-footprint and with less communication overhead than using Merkle Trees.&lt;/p&gt;
</style></abstract></record></records></xml>