Optimized OR-Sets without ordering constraints

Mukund, Madhavan ; Shenoy R., Gautham ; Suresh, S. P. (2014) Optimized OR-Sets without ordering constraints In: International Conference on Distributed Computing and Networking (ICDCN) 2014, 04-07 Jan 2014, Coimbatore, India.

Full text not available from this repository.

Official URL: https://link.springer.com/chapter/10.1007/978-3-64...

Related URL: http://dx.doi.org/10.1007/978-3-642-45249-9_15


Eventual consistency is a relaxation of strong consistency that guarantees that if no new updates are made to a replicated data object, then all replicas will converge. The conflict free replicated datatypes (CRDTs) of Shapiro et al. are data structures whose inherent mathematical structure guarantees eventual consistency. We investigate a fundamental CRDT called Observed-Remove Set (OR-Set) that robustly implements sets with distributed add and delete operations. Existing CRDT implementations of OR-Sets either require maintaining a permanent set of “tombstones” for deleted elements, or imposing strong constraints such as causal order on message delivery. We formalize a concurrent specification for OR-Sets without ordering constraints and propose a generalized implementation of OR-sets without tombstones that provably satisfies strong eventual consistency. We introduce Interval Version Vectors to succinctly keep track of distributed time-stamps in systems that allow out-of-order delivery of messages. The space complexity of our generalized implementation is competitive with respect to earlier solutions with causal ordering. We also formulate k-causal delivery, a generalization of causal delivery, that provides better complexity bounds.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
ID Code:114136
Deposited On:25 May 2018 04:55
Last Modified:25 May 2018 04:55

Repository Staff Only: item control page