Loading...
Please wait, while we are loading the content...
Similar Documents
Dotted Version Vectors: Efficient Causality Tracking for Distributed Key-Value Stores
| Content Provider | Semantic Scholar |
|---|---|
| Author | Moreno, Carlos Baquero Fonte, Vitor Gonçalves, Ricardo Almeida, Paulo Sérgio Preguiça, Nuno M. |
| Copyright Year | 2012 |
| Abstract | In cloud computing environments, data storage systems often rely on optimistic replication to provide good performance to geographically disperse users and to allow operation even in the presence of failures or network partitions. In this scenario, it is important to be able to accurately and efficiently identify updates executed concurrently. In this paper, first we review, and expose problems with current approaches to causality tracking in optimistic replication: these either lose information about causality or do not scale, as they require replicas to maintain information that grows linearly with the number of clients or updates. Then, we propose a novel, scalable solution that fully captures causality: it maintains very concise information that grows linearly only with the number of servers that register updates for a given data element, bounded by the degree of replication. Moreover, causality can be checked in O(1) time instead of O(n) time for version vectors. We have integrated our solution in Riak, and results with realistic benchmarks show that it can use as little as 10% of the space consumed by current version vector implementation, which includes an unsafe pruning mechanism. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://gsd.di.uminho.pt/members/vff/dotted-version-vectors-2012.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
