@conference {3596,
	title = {DottedDB: Anti-Entropy without Merkle Trees, Deletes without Tombstones},
	booktitle = {36th IEEE International Symposium on Reliable Distributed Systems },
	series = {SRDS 2017},
	year = {2017},
	month = {28 September},
	publisher = {IEEE},
	organization = {IEEE},
	address = {Hong Kong, China},
	abstract = {<p>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.</p>
},
	attachments = {https://haslab.uminho.pt/sites/default/files/tome/files/dotteddb_srds.pdf},
	author = {Ricardo Gon{\c c}alves and Paulo S{\'e}rgio Almeida and Carlos Baquero Moreno and Vitor Fonte}
}