A Fast Operational Transformation Algorithm for Mobile and Asynchronous Collaboration
A Fast Operational Transformation Algorithm for Mobile and Asynchronous Collaboration
复制标题
DOI：
10.1109/tpds.2010.64
复制
发表时间：
2010-12
影响因子：
5.3
通讯作者：
Bin Shao;Du Li;Ning Gu
中科院分区：
文献类型：
--
作者：
Bin Shao;Du Li;Ning Gu
在移动协作环境中，共享文件经常被复制，以便用户可以在断开连接期间并行工作。当重新连接时，不同用户所做的更新序列将被合并，以生成共享文件的一致视图。提出了一种支持移动协作的基于变换的合并算法。与其他乐观一致性控制方法相比，它可以以最细的粒度自动将任何更新合并到同一文件，而不会造成工作损失。此外，它提高了最先进的基于变换的合并算法的时间复杂度，从O（n3）到O(n)，其中n是任意一个序列的大小，当它们的大小是可比较的。这一改进是巨大而重要的，特别是对于使用电池且处理能力有限的移动设备。
In a mobile collaboration environment, the shared files are often replicated so that the users can work in parallel during periods of disconnection. When reconnected, sequences of updates made by different users are merged to produce a consistent view of shared files. This paper presents a novel transformation-based merging algorithm for supporting mobile collaboration. Compared to alternative optimistic consistency control methods, it can merge any updates to the same file automatically at the finest granularity without causing loss of work. Moreover, it improves the time complexity of the state-of-the-art transformation-based merging algorithms from O(n3) to O(n), where n is the size of either sequence when their sizes are comparable. This improvement is drastic and important especially for mobile devices that run on batteries and have limited processing power.