协同组编辑环境中的数据一致性维护方法

协同组编辑环境中的数据一致性维护方法学生：杨江明导师：顾宁教授计算机与信息技术系

2022年11月14日1内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日2内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日3背景及问题的提出协同组编辑是一个抽象的研究模型传统的协同组编辑。GroupSketch（GreenbergandBohnet）、Grove（Ellis,Gibbs,andRein）、ShrEdit（McGuffinandOlson）、DistEdit（KnisterandPrakash）、REDUCE(SubandEllis)单机软件的协同化。ICT(D.LiandR.Li)、CoWord&CoPowerpoint(Xiaetal.)、CoAutoCAD(Guetal.)基于Web2.0的非实时组编辑。CDVE2007(ShenandSun)2022年11月14日4背景及问题的提出协同组编辑环境下问题结果的一致性问题。如果操作是不可交互的，则不同的操作执行顺序会导致不同的结果。操作的依赖性问题。需要保证操作的执行条件操作的意愿维护问题。假设初始状态为“ABC”。在SR1，O3为Insert[“d”,1]，即将”d“插入到位置1(即A和B之间)；而在SR3，O1为Insert[”e“,2]，即将”e“插入到位置2(即B和C之间)。当O1

到达SR1

时，该站点已经被操作O3修改成”AdBC“，直接执行O1会把字符e插入到字符d和B之间，这显然是错误的。事务的支持性问题。2022年11月14日5内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日6数据及操作表示线性结构线性结构是多种数据类型的抽象表示。直观上的线性结构包括：字符串，链表等数据结构。但事实上，线性结构维护的是多个对象间的一个全序关系，而这样一种全序关系是广泛存在的。全序关系的维护是协同环境下一致性维护的基础。树型结构一些主流的文档类型需要树型结构的表示。通过XML可以支持基于关系的操作，是Web应用的需求。2022年11月14日7一致性模型因果关系维护（Causalitypreservation）：所有操作的执行顺序都按照它们之间的因果关系。对于任意的两个操作O1和O2，如果O1→O2，则在所有的站点，操作O1都在操作O2之前执行。一致性维护（Convergence）：当相同的操作在所有的站点都执行完成之后，所有的数据副本保持一致。意愿维护（Intentionpreservation）：任何一个操作在任何站点的执行效果都保持和它产生站点一致。2022年11月14日8内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日9回溯思想2022年11月14日10线性结构的回溯过程2022年11月14日11线性结构的回溯过程对难题的解决操作转换方法中TP2条件维护的困难dOPT难题假设几个插入操作都是面向相同的位置，操作之间满足因果顺序或者是并发的。仅仅依靠强制规定操作间的优先级是无法保证结果的收敛性的。False-tie难题假设两个并发的插入操作可能会因为在它们之间一个并发的删除操作，而丢失它们之间的左右位置关系，并且可能得到一个相反的结果。证明过程2个操作N个操作2022年11月14日12树型结构的回溯过程2022年11月14日13树型结构的回溯过程已有方法的不足操作转换方法（OperationTransformation）方法无法支持关系操作。基于锁和序列化的方法无法满足操作的响应时间和自由度。证明过程2个操作N个操作2022年11月14日14内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日15一致性维护的相关问题操作的历史队列通过状态向量表，精简操作的历史队列Undo操作支持通过在回溯过程添加计数器，是回溯过程可以考虑Undo操作支持单站点并发操作的时间戳模型通过分离考虑操作间关系和操作的执行状态，引入两个时间戳，支持操作的并发执行。事务操作的支持2022年11月14日16事务操作的支持2022年11月14日17内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2022年11月14日18线性结构效率分析线性结构优化，通过调整数据结构，可以优化计数效率平摊效率插入操作的开销可以表示为O(h×logn+logn+d×h+h+d+m)，删除操作的开销为O(h×logn+logn+d×h+h+d)其中h为历史队列长度，n为文档字符数，d为针对一个节点的操作数2022年11月14日19树型结构效率分析2022年11月14日20原型系统2022年11月14日21内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结2022年11月14日22总结本文的工作基于状态转换的一致性维护方法一致性维护的四个相关问题算法的理论分析和实验CoAutoCAD演示系统进一步的工作关系数据库的协同化支持动态性的加入、退出进一步改善操作执行的并发性处理用户意愿的矛盾2022年11月14日23攻读硕士学位期间的科研工作读硕士期间已发表和已录用的论文顾宁，杨江明，张琦炜.协同组编辑中基于地址空间转换的一致性维护方法.计算机学报，第30卷，第5期，2007年5月,763-774页.杨江明，张琦炜，顾宁.数据网格中复制式数据的一致性维护方法.华中科技大学学报（自然科学版）.Vol.34,SupI,2006年9月,49-52页.ShichaoZhang,NingGu,JiangmingYang.AnNorm-drivenStateMachineModelforCSCWSystems.ExpertSystemsWithApplications,Volume31,Issue4,November2006,Pages800-807.JiangmingYang,QiweiZhang,NingGu.AConsistencyMaintenanceApproachinReplicatedServices.InProceedingsof2006IEEEinternationalconferenceoncomputerandinformationtechnology,Seoul,Korea,Sept2006.QiweiZhang,JiangmingYang,NingGu,YuweiZong,ZhigangDing,ShaohuaZhang.DynamicReplicaLocationServiceSupportingDataGridSystems.InProceedingsof2006IEEEinternationalconferenceoncomputerandinformationtechnology,Seoul,Korea,Sept2006.ShichaoZhang,JiangmingYang,NingGu.GridSM:aNorm-drivenStateMachineModelofGridWorkflow.InProceedingsofInternationalConferenceonCSCWD2006,Nanjing,China,May,2006.杨江明，顾宁，吴筱媛.基于地址空间转换方法的Undo操作支持.通信学报，第27卷，2006年3月，48-56页。2022年11月14日24攻读硕士学位期间的科研工作读硕士期间已发表和已录用的论文NingGu,JiangmingYang,QiweiZhang.Consistencymaintenancebasedonthemark\&retracetechniqueingroupwaresystems.InProceedingsofthe2005internationalACMSIGGROUPconferenceonSupportinggroupwork,SanibelIsland,USA,pages264-273,Nov2005.NingGu,JunXu,XiaoyuanWu,JiangmingYang,andWeiYe.Ontologybasedsemanticconflictsresolutionincollaborativeeditingofdesigndocuments.InternationalJournalofAdvancedEngineeringInformatics(IJAEI),19(2),103-111,2005.JiangmingYang,QiweiZhang,NingGu,GenxingYang,andZhenyuLiu.Themulti-versionandsingle-displaystrategyinundoscheme.InProceedingsofthe5thinternationalconferenceoncomputerandinformationtechnology,pages290-296,September2005,Shanghai,China.张琦炜，杨江明，顾宁，杨根兴，刘振宇.数据网格中的动态分布式多入口技术.计算机科学，第32卷，2005年7月增刊A，127-131页。JiangmingYang,NingGuandXiaoyuanWu.Adocumentmarkbasedonmethodsupportinggroupundo.InInternationalWorkshoponCollaborativeEditingSystems,ACMCSCW’2004,November2004,Chicago,USA.NingGu,JunXu,XiaoyuanWuandJiangmingYang.Asolutiontothesemanticconflictsinthecollaborativeeditingofdesigndocuments.InProceedingsofInternationalConferenceonCSCWD2004,VolumeIIpages179-185,May2004,Xiamen,China.ShuoWang,FengJing,JianmgingYang,JiboHe.LongQuerySuggestionList:PrioritizedorOrganized?InHCIInternationalConference2007.Accepted.2022年11月14日25攻读硕士学位期间的科研工作专利及软件著作权(专利)顾宁、张世超、徐寅俊、杨江明.一种规范驱动的网格工作流描述和验证方法.专利申请号：2.2,专利申请日：2005年7月15日,公开号：CN1719832(专利)顾宁、杨江明、张琦炜、绍斌.标记回溯的一致性维护方法.专利申请号：2.1,专利申请日：2006年4月13日,公开号：CN1831776(专利)顾宁、杨江明、张琦炜.面向XML的标记回溯的一致性维护方法.专利申请号：2.4,专利申请日：2006年5月11日,公开号：CN1845076(计算机软件著作权)软件名称：网格工作流管理系统软件V1.0,编号：软著登字第039155号,登记号：2005SR07