实时协同中的一致性维护关键技术

doi:10.3969/j.issn.1000-3428.2010.22.001

计算机工程 ›› 2010, Vol. 36 ›› Issue (22): 1-6. doi: 10.3969/j.issn.1000-3428.2010.22.001

所属专题：特邀论文；

• 特邀论文 • 下一篇

实时协同中的一致性维护关键技术

邵斌，卢暾，顾宁

（复旦大学计算机科学技术学院，上海 201203）

出版日期:2010-11-20 发布日期:2010-11-20
作者简介:邵斌(1982－)，男，2010年复旦大学博士毕业，现任微软亚洲研究院副研究员，主研方向：CSCW，Web信息抽取；卢暾，博士、复旦大学计算机科学技术学院讲师，主研方向：协同计算；顾宁，复旦大学计算机科学技术学院教授、博士生导师，主研方向：CSCW中的一致性维护，社会网络的数据分析，云计算平台技术
基金资助:
国家自然科学基金资助项目(60736020, 60803118)

Key Techniques of Consistency Maintenance in Real-time Collaboration

SHAO Bin, LU Tun, GU Ning

（School of Computer Science, Fudan University, Shanghai 201203, China）

Online:2010-11-20 Published:2010-11-20

摘要/Abstract

摘要：

实时协同广泛采用数据复制技术来隐藏网络延迟、提高响应速度和改善交互体验。在复制式结构中，用户可以无约束地在不同数据副本上进行操作，这必然会引发一致性维护问题。针对上述问题，根据实时协同应用的特点和需求，总结一致性维护研究面临的技术挑战，通过研究实时协同中操作转换、地址空间转换和WOOT一致性维护的关键技术，讨论Undo和String转换等难点问题，分析这些关键技术在单用户软件向多用户协同软件透明转换、Web2.0环境和移动协同环境中的应用情况。

关键词: 实时协同, 一致性维护, 一致性模型, 操作转换, 地址空间转换

Abstract:

Data replication is widely used to hide network latency, enhance response time and improve interaction experience in real-time collaboration. Users can operate on data replicas unconstrainedly, which results in consistency maintenance problems of these replicas. Aiming at the problem, this paper introduces the challenges of consistency maintenance according to the features and requirements of real-time collaboration applications. By analyzing representative key techniques of operation transformation, address space transformation and WOOT, it elaborates the challenging problems such as Undo and String transformation, and details how these key techniques are applied in the transparent adaptation from single-user applications to collaborative ones, Web 2.0 and mobile collaboration environments.

Key words: real-time collaboration, consistency maintenance, consistency model, Operational Transformation(OT), address space transformation

中图分类号:

TP391

邵斌, 卢暾, 顾宁. 实时协同中的一致性维护关键技术[J]. 计算机工程, 2010, 36(22): 1-6.

SHAO Bin, LEI Tun, GU Ning. Key Techniques of Consistency Maintenance in Real-time Collaboration[J]. Computer Engineering, 2010, 36(22): 1-6.

https://www.ecice06.com/CN/Y2010/V36/I22/1

参考文献

[1] Joslin C, Molet T, Magnenat-Thalmann N. Advanced Real-time Collaboration over the Internet[C]//Proc. of the ACM Symposium on Virtual Reality Software and Technology. New York, USA: ACM Press, 2000.
[2] Olson G M, Zimmerman A, Bos N. Scientific Collaboration on the Internet[M]. [S. l.]: The MIT Press, 2008.
[3] Jara C A, Candelas F A, Torres F, et al. Real-time Collaboration of Virtual Laboratories Through the Internet[J]. Computer Education, 2009, 52(1): 126-140.
[4] Saito Y, Shapiro M. Optimistic Replication[J]. ACM Computing Survey, 2005, 37(1): 42-81.
[5] Ellis C A, Gibbs S J. Concurrency Control in Groupware Systems[C]//Proc. of SIGMOD’89. New York, USA: ACM Press, 1989.
[6] Sun Chengzheng, Ellis C. Operational Transformation in Real-time Group Editors: Issues, Algorithms, and Achievements[C]// Proc. of CSCW’98. New York, USA: ACM Press, 1998.
[7] Gu Ning, Yang Jiangming, Zhang Qiwei. Consistency Maintenance Based on the Mark & Retrace Technique in Groupware Systems[C]//Proc. of GROUP’05. New York, USA: ACM Press, 2005.
[8] Oster G, Urso P, Molli P, et al. Data Consistency for P2P Collaborative Editing[C]//Proc. of CSCW’06. New York, USA: ACM Press, 2006.
[9] Hymes C M, Olson G M. Unblocking Brainstorming Through the Use of Simple Group Editor[C]//Proc. of CSCW’92. [S. l.]: ACM Press, 1992.
[10] Vidot N, Cart M, Ferrie J, et al. Copies Convergence in a Distributed Real-time Collaborative Environment[C]//Proc. of CSCW’00. New York, USA: ACM Press, 2000.
[11] Li Du, Li Rui. Preserving Operation Effects Relation in Group Editors[C]//Proc. of CSCW’04. New York, USA: ACM Press, 2004.
[12] Nichols D A, Curtis P, Dixon M, et al. High-latency, Low- bandwidth Windowing in the Jupiter Collaboration System[C]// Proc. of UIST’95. Pittsburgh, Pennsylvania, USA: ACM Press, 1995.
[13] Ressel M, Nitsche-Ruhland D, Gunzenhauser R. An Integrating, Transformation-oriented Approach to Concurrency Control and Undo in Group Editors[C]//Proc. of CSCW’96. New York, USA: ACM Press, 1996.
[14] Suleiman M, Cart M, Ferrie J. Concurrent Operations in a Distributed and Mobile Collaborative Environment[C]//Proc. of ICDE’98. Washington D.C., USA: IEEE Computer Society, 1998.
[15] Sun Chengzheng, Jia Xiaohua, Zhang Yanchun, et al. Achieving Convergence, Causality-preservation, and Intention Preservation in Real-time Cooperative Editing Systems[J]. ACM Transactions on Computer-Human Interaction, 1998, 5(1): 63-108.
[16] Li Rui, Li Du. Commutativity-based Concurrency Control in Groupware[C]//Proc. of CollaborateCom’05. San Jose, USA: [s. n.], 2005.
[17] Sun David, Sun Chengzheng. Operation Context and Context-based Operational Transformation[C]//Proc. of CSCW’06. New York, USA: ACM Press, 2006.
[18] Sun David, Sun Chengzheng. Context-based Operational Transformation in Distributed Collaborative Editing Systems[J]. IEEE Transactions on Parallel Distributed System, 2009, 20(10): 1454-1470.
[19] Lamport L. Time, Clocks, and the Ordering of Events in a Distributed System[J]. Communications of ACM, 1978, 21(7): 558-565.
[20] Li Rui. Operational Transformation-based Concurrency Control in Group Editors[D]. Texas, USA: Texas A&M University, 2006.
[21] Li Du, Li Rui. An Admissibility-based Operational Transformation Framework for Collaborative Editing Systems[J]. Computer Supported Coopertive Work, 2010, 19(1): 1-43.
[22] Oster G, Molli P, Urso P, et al. Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems[C]//Proc. of CollaborateCom’06. Atlanta, Georgia, USA: IEEE Computer Society, 2006.
[23] 邵斌. 高效的操作转换一致性维护方法研究[D]. 上海: 复旦大学, 2010.
[24] Prakash A, Knister M J. A Framework for Undoing Actions in Collaborative Systems[J]. ACM Transactions on Computer-Human Interaction, 1994, 1(4): 295-330.
[25] Dewan P, Choudhary R. Coupling the User Interfaces of a Multiuser Program[J]. ACM Transactions on Computer Human Interaction, 1995, 2(1): 1-39.
[26] Sun Chengzheng. Undo as Concurrent Inverse in Group Editors[J]. ACM Transactions on Computer-Human Interaction, 2002, 9(4): 309-361.
[27] 杨江明, 顾宁, 吴筱媛. 基于地址空间转换方法的Undo操作支持[J]. 通信学报, 2006, 27(3): 48-56.
[28] Shao Bin, Li Du, Gu Ning. An algorithm for Selective Undo of Any Operations in Collaborative Applications[C]//Proc. of GROUP’10. Sanibel Island, USA: [s. n.], 2010.
[29] Shao Bin, Li Du, Gu Ning. ABTS: A Transformation-based Consistency Control Algorithm for Wide-area Collaborative Applications[C]//Proc. of CollaborateCom’09. Washington D. C., USA: IEEE Computer Society, 2009.
[30] Shao Bin, Li Du, Gu Ning. An Optimized String Transformation Algorithm for Real-time Group Editors[C]//Proc. of ICPADS’09. Washington D. C., USA: IEEE Computer Society, 2009.
[31] Xia Steven, Sun David, Sun Chengzheng, et al. Leveraging Single-user Applications for Multi-user Collaboration: The Coword Approach[C]//Proc. of CSCW’04. New York, USA: ACM Press, 2004.
[32] Sun Chengzheng, Xia Steven, Sun David, et al. Transparent Adaptation of Single-user Applications for Multi-user Real-time Collaboration[J]. ACM Transactions on Computer-Human Interaction, 2006, 13(4): 531-582.
[33] Welcome to CoPowerPoint: A Real-time Collaborative Multimedia Slides Creation and Presentation System[Z]. [2010-05-11]. http:// cooffice.ntu.edu.sg/copowerpoint/.
[34] Zheng Yang, Shen Haifeng, Sun Chengzheng. Leveraging Single-user AutoCAD for Collaboration by Transparent Adaptation[C]//Proc. of CSCWD’09. Santiago, Chile: [s. n.], 2009.
[35] Agustina A, Liu Fei, Xia Steven, et al. CoMaya: Incorporating Advanced Collaboration Capabilities into 3D Digital Media Design Tools[C]//Proc. of CSCW’08. San Diego, USA: [s. n.], 2008.
[36] CoEclipse[Z]. [2010-06-21]. http://www3.ntu.edu.sg/home/czsun/ projects/coeclipse/.
[37] Yang Jiangming, Wang Haixun, Gu Ning, et al. Lock-free Consistency Control for Web2.0 Applications[C]//Proc. of WWW’08. New York, USA: ACM Press, 2008.
[38] Shao Bin, Li Du, Gu Ning. A Sequence Transformation Algorithm for Supporting Cooperative Work on Mobile Devices[C]//Proc. of CSCW’10. Savannah, USA: [s. n.], 2010.

选择文件类型/文献管理软件名称

选择包含的内容

实时协同中的一致性维护关键技术

Key Techniques of Consistency Maintenance in Real-time Collaboration

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	吕正, 陈昊, 陈峰, 吕毅. MOTEC: 一个存储一致性模型验证工具[J]. 计算机工程, 2012, 38(11): 242-246.
[2]	蒋试伟;欧阳松. 基于副本索引的P2P副本一致性维护策略[J]. 计算机工程, 2008, 34(19): 123-126.
[3]	路勋;高亮;邱浩波;丁大伟. 三维协同设计系统中实时协同的研究与实现[J]. 计算机工程, 2007, 33(20): 283-封三.
[4]	吴青;翟建设;杨剑勇. 基于二维有序状态向量的协同操作转换算法[J]. 计算机工程, 2007, 33(02): 50-52.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

实时协同中的一致性维护关键技术

Key Techniques of Consistency Maintenance in Real-time Collaboration

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价