协同图形编辑系统中的并发控制研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
分布环境下的协同图形编辑系统OCES(Object-based Cooperative graphics Editing System)是计算机支持的协同工作CSCW(Computer Supported Cooperative Work)中一个十分活跃的研究方向。为了支持自然、自由的协同编辑,OCES具有分布的用户群、实时响应、协作透明性和无约束性等特征,为此大部分系统采用全复制的体系结构。研究与开发复制式体系结构下的OCES的关键问题之一是多个复制数据视图的一致性,这也是本文研究的核心。
     本文首先介绍了协同编辑系统的一致性维护技术。围绕协同编辑系统的一致性模型,具体讨论了一致性模型的三个一致性特征及可行的保证技术,并考察了一些典型的一致性维护策略。
     然后介绍了基于对象复制的多版本策略,在分析其多版本增创算法性能缺陷的基础上给出了基于冲突组概念的新的分布式多版本递增创建算法,减少了相容操作的比较次数、避免了版本冗余问题,提高了算法的性能。
     随后介绍了基于版本复制的多版本策略,其解决了对象复制策略所不能克服的一些复杂问题。提出了改进的基于版本复制多版本策略,实现了操作的层次存储,最大程度上避免了同一个操作被存储在多个版本中,减少了系统的操作存储量。
     最后简要分析了版本间冲突操作的产生情况,提出了使用子树构造法来保证版本间冲突操作的执行意愿,并首次提出了广义最大冲突组的概念,给出了一个利用广义最大冲突组实现版本间冲突操作的分布式算法。
     原型系统CoWork从系统实现的角度论证了上述策略和算法的正确性。文中还简要分析了CoWork涉及的其它支持策略,以及CoWork的系统性能。
The Object-based Cooperative graphics Editing System (OCES) in distributed environment is now a very active research area of CSCW (Computer Supported Cooperative Work). To support free and natural interaction, this kind of system should have such characteristics as collaborative distribution, interactive in real-time and operation's non-restriction. In order to satisfy these features, the fully replicated architecture should be adopted. One of the key problems in studying and designing the replicated collaborative editing system is the consistency of the multi-duplicated data view, and which is also the core discussed in this thesis.
     Technologies supporting consistency preservation based on a consistency model, which includes three consistency properties, are first surveyed. Our focus is how these properties are maintained. Several representative consistency schemes explored by other researchers are also introduced.
     Then a multi-versioning scheme based on object replication is discussed. Based on analysis of the performance limitation of the distributed algorithm for multiple versions incremental creation, a new algorithm using conflict set is proposesd which not only can decrease the comparison-number of compatible operations, but also can avoid the operation of removing the redundant object versions. The theory certification and simulation experiment results shows that performance of the new algorithm is more efficient than the original algorithm.
     Then a distributed collaborative multi-versioning scheme based on version replication, which can resolve some complex problems that the object-replication can not deal with, is discussed in detail. An improved multi-versioning using hierarchical storage strategy for operations is proposed to avoid same operation to be stored in different versions to the largest degree and reduce the number of operation stored in system.
     At last, this paper analyses the conflict operations between multi-versions, and proposes an idea of subtree construction to preserve the intention of these conflict operations. This paper first proposes a conception of generalized max conflict set, and uses it to realize the confict operation between muilti-versions.
     A prototype system CoWork is designed and implemented as a test-bed for the correctness of proposed strategies and algorithms. Other related cooperative techniques used in this prototype, as well as their runtime performance, are also discussed briefly in the end of this thesis.
引文
[1] C.A.Ellis, S.J.Gibbs. Concurrency control in groupware systems. In proc. of ACM SIGMOD International Conference on Management of Data, May 1989: 399-407.
    [2] Sun C Z, X Jia, Y Zhang, Y Yang, and D Cben. Achieving convergence, causality-preservation, and intention-preservation in real time cooperative editing systems. ACM Transaction on Computer-Human Interactions, 1998, 5(1): 63-108.
    [3] David C and Sun C Z. A distributed algorithm for graphic objects replication in real-time group editors. In proc. of ACM International Conference on Supporting Group Work, Nov 14-17, 1999, Phoenix, Arizona, USA.
    [4] Yun Yang, Sun C Z, Yanchun Zhang, Xiaohua Jia. Real-Time Cooperative Editing on the Internet, IEEE Internet Computing May-June 2000:18-25.
    [5] James Michael Allen Begole. Flexible Collaboration Transparency: Supporting Worker Independence in Replicated Application-Sharing Systems. Ph.D. Thesis. The Virginia Polytechnic Institute and State University, 1998.
    [6] 肖波,张东,诸洪文.计算机支持的协同工作并发控制策略.上海交通大学学报,Vol.33No.1, Jan.1999,pp.101-103.
    [7] 郭学旭,王云鹏,潘翔,雷毅.计算机辅助协同设计系统并发控制机制的研究.计算机辅助设计与图形学学报.Vol.16.No.2 Feb.2004:201-205.
    [8] Sun C Z and David Chen. Intention preservation by object replication in cooperative graphics editing systems. Journal of Applied Systems Studies, Vol. 1, No.3, 2000:345-360.
    [9] Sun C Z and Ellis C A. Operational transformation in real-time group editors: issues, algorithms, and achievements. In Proc. of ACM Conference on Computer Supported Cooperative Work, Seattle, USA, Nov 1998: 59-68.
    [10] 杨光信,史美林.全复制结构下基于对象数据模型的并发控制.计算机学报,23(2),200012:113-125.
    [11] Munson J, Dewan P. A concurrency control framework for collaborative system. Proceediags of ACM Conference on Computer Supported Cooperative Work. Cambridge, 1996.pp.278-287.
    [12] Saul Greenberg and David Marwood. Real time groupware as a distributed system: concurrency control and its effect on the interface. In Proc. of ACM Conference on Computer- Supported Cooperative Wock CSCW'94, Oct 22-26, 1994, North Carolina, ACM Press.
    [13] 史美林,向勇.计算机支持的协同工作理论与应用.电子工业出版社,2000.
    [14] 王邦,朱光喜.多媒体协同编辑中的共享粒度的研究与实现.计算机工程与应用,2000.2.
    [15] 詹永照,毛启容,宋顺林.基于相对位置的分布式实时协同编辑乐观锁并发控制算法.计算机科学、003,7(30):126-129.
    [16] 毛启容,王进峰,詹永照.相对位置乐观锁机制及在协同编辑中的应用.计算机辅助设计与图形学学报,Vol.16.No.9,Sep.2004:1307-1312.
    [17] 窦万峰,张子瑜,谢立.面向图形对象的协同编辑系统的并发操作冲突检测.小型微型计算机系统,Vol.24 No.7,July.2003,pp.1157-1160.
    [18] David Chen and Sun C Z. Optional instant locking in distributed collaborative graphics editing systems. In Proc. of 8~(th) International Conference on Parallel and Distributed. Systems (ICPADS 2001), pp.26-29, June.2001, KyongJu City, Korea.
    [19] David Chen. Consistence in collaborative graphics editing systems. Ph.D. Thesis. School of Computing and Information Technology, Griffith University, Brisbane. Australia, 2001.
    [20] L.Y. Xue, K. Zhang, and C. Sun. Conflict Control Locking In Distributed Cooperative Graphics Editing Systems. Proc.WISE' 2000-1st International Conference on Web Information Systems Engineering, Vol.l, pp.401-408, Hong Kong, China, pp.19-20 June, 2000, IEEE CS Press.
    [21] Dourish. P. Consistency guarantees: Exploiting application semantics for consistency management in a collaboration toolkit. In Proc. of ACM Conference on Computer-Supported Cooperative Work CSCW'96 (Boston, Mass), New York: ACM.
    [22] Li Du, Zhou Li-min, Richard R. Muntz and Sun Cheng-zheng. Operation Propagation in Real-Time Group Editors. IEEE Multimedia, 2000, 7(4):55-61.
    [23] Xueyi Wang, Jiajun Bu, Chun Chen. A new consistency model in collaborative editing systems. In proc. of the 4~(th) International Workshop on Collaborative Editing, New Orleans, USA, 2002.
    [24] Michel Raynal, Mukesh Singhal. Logical time: Capturing causality in distributed systems. IEEE Computer Magazine 29, Feb. 1996: 49-56.
    [25] M.Singhal and A.Kshemkalyani. An Efficient hnplementa-of Vector Clocks. Information ProcessingLetters, Vol. 43, Ang. 1992: 47-52.
    [26] 何鸿君,吴泉源,罗莉.协同编辑中维护意愿的文档标注方法,软件学报,10(2), 1999.2: 160-163.
    [27] Liyin Xue, Mehmet Orgun, and Kang Zhang. A user-centered consistency model in read-time collaborative editing systems. In proc. of the 4~(th) International conference on Distributed Communities on the Web, April 3-5, 2000, Sydney, Australia.
    [28] Hala Skaf-Molli, Pascal Molli and Gerald Osier. Semantic Consistency for Collaborative Systems. In Proc. of the Fifth International Workshop on Collaborative Editing Systems, Helsinki, September 15, 2003.
    [29] Liyin Xue, Mehmet Orgun, and Kang Zhang. Group-based time-stamping scheme for the preservation of group intention. In proceeding of the 4~(th) International conference on Distributed Communitics on the Web, Sydney, April.2002:125-137.
    [30] 余文芳,姜波.实时图案协同设计中冲突问题的研究.计算机辅助设计与图形学学报,Vol.17,No.7, July.2005,pp.1588-1592.
    [31] 施尉霁,尹建伟,陈刚,董金祥.基于图形编辑的实时协同设计系统中的同步性问题研究.计算机工程与应用,Vol.40,No.20.2004:95-98.
    [32] 高曙明,何发智.分布式协同设计技术综述.计算机辅助设计与图形学学报,Vol.16,No.2 Feb.2004(2),PP.149-157.
    [33] Sun C Z and David Chen. Consistency maintenance in real-time collaborative graphics editing systems. ACM Transactions on Computer-Human Interaction, Vol.9, No.l, March 2002:1-41.
    [34] 窦万峰,李春萍.多版本技术中的对象标识及其压缩.软件学报,2004,15(8):1133-1140.
    [35] 李春萍,窦万峰,李桂香:基于多版本的对象标识与垃圾收集算法.小型微型计算机系统.Vol.25,No.12.Dec.2004.pp.2247-2250.
    [36] 秦彬绢,滕逸龙,陈良宽,张昆.协同图形编辑系统中一种改进的多版本递增创建算法.小型微型计算机系统,Vol.24,No.12.Dec.2003,pp.2283-2285.
    [37] L.Y.Xue, K.Zhang, and C.Shn. An Integrated Post-locking, Multi-versioning, and Transformation Scheme for Consistency Maintenance in. Real-time Group Editors. Proc. of International Symposium on Autonomous Decentralized Systems (ISADS), IEEE Computer Society Press, 2001, pp.56-64.
    [38] Liyin Xue and Mehmet Orgun. An Exclusive Version Locking Scheme. in Internet-based Real-time Group Editors. in Proceedings of the 2003 Symposium on applications and the Interact (SAINT 2003), IEEE Computer Society,, New Jersey, USA 2003, pp.94-101.
    [39] Liyin Xue, Mehmet Orgun and Kang Zhang. Editing Any Version at Any Time: a consistency maintenance mechanism in Internet-based collaborative environments. In Proceedings of Ninth International Conference on Parallel and Distributed Systems, 2002, Taiwan, ROC: 69-74.
    [40] Liyin Xue, Mehmet Orgnn and Kang Zhang. A Multi-versioning Algorithm fbr Intention Preservation in Distributed Real-time Group Editors , in Proceedings of the twenty-sixth Australasian computer science conference, Australian Computer Society, Sydney, Australia 2003, pp.19-28,
    [41] Sun Chengzheng. Undo any operation at any time in group editors, lu Proceedings of ACM conf. On CSCW'00, Philadelphia, PA, USA, DEC.2000, pp. 191-200.
    [42] Chen D, Sun C. Undoing any operation in collaborative graphics editing systems. In Proceedings of ACM 2001 confi On Supporting Group work, Boulder, Colorado, USA, Sep. 30-Oct.3, 2001, pp.197-206.
    [43] Sun C. Undo as concurrent inverse in group editors. ACM Trans. On Computer-Human Interaction, 2002, 9(4): 309-361.
    [44] Xueyi Wang, Jiajun Bu, and Chun Chen. Research on conflict resolution and operation consistency in real-time collaborative graphic designing system. In the 7th International Conference on Computer Supported Cooperative Work in Design, 2002:145-150.
    [45] 沈奇,窦万峰.协同多版本技术中原始版本及其表示和效果显示,金陵科技学院学报2005,21(1):19-23.
    [46] 沈奇,窦万峰.协同多版本技术中的中间版本.计算机与现代化,2005年第10期:47-50.
    [47] Wanfeng Dou, Ming Zhu, Qi Shen. Cooperative multi-versioning technique based on version replication. Proc. Oc the 10~(th) International Con on Computer Supported Cooperative work in Design, May 3-5, Nanjing, China, 2006:159-164.
    [48] 沈奇.分布协同多版本控制技术.南京师范大学硕士研究生论文,2005.
    [49] 李春萍.分布环境下的协同图形编辑系统研究.南京师范大学硕士研究生论文.2004

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700