An Efficient Approach to Move Elements in a Distributed Geo-Replicated Tree

Anjana, Parwat Singh and Chandrassery, Adithya Rajesh and Peri, Sathya (2022) An Efficient Approach to Move Elements in a Distributed Geo-Replicated Tree. In: 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2022, 16 May 2022 through 19 May 2022, Taormina.

[img] Text
CCGrid_2022.pdf - Published Version
Available under License Creative Commons Attribution.

Download (129kB)


Replicated tree data structures are extensively used in collaborative applications and distributed file systems, where clients often perform move operations. Local move operations at different replicas may be safe. However, remote move operations may not be safe. We present an efficient algorithm to perform move operations on the distributed replicated tree while ensuring eventual consistency. The proposed technique is primarily concerned with resolving conflicts efficiently, requires no interaction between replicas, and works well with network partitions. We use the last write win semantics for conflict resolution based on globally unique operation timestamps. The proposed solution requires only one compensation operation to avoid cycles being formed when move operations are applied. The proposed approach achieves an effective speedup of 14.6-68.19× over the state-of-the-art approach in a geo-replicated setting. © 2022 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Conflict-free Replicated Data Types; Distributed File Systems; Eventual Consistency; Replicated Tree
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 19 Aug 2022 09:29
Last Modified: 19 Aug 2022 09:29
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10230 Statistics for this ePrint Item