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

协同组编辑环境中的数据一致性维护方法学生：杨江明导师：顾宁教授计算机与信息技术系2019年9月13日2019年9月13日复旦大学信息科学与工程学院2内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院3内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院4背景及问题的提出协同组编辑是一个抽象的研究模型传统的协同组编辑。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)2019年9月13日复旦大学信息科学与工程学院5背景及问题的提出协同组编辑环境下问题结果的一致性问题。如果操作是不可交互的，则不同的操作执行顺序会导致不同的结果。操作的依赖性问题。需要保证操作的执行条件操作的意愿维护问题。假设初始状态为“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之间，这显然是错误的。事务的支持性问题。2019年9月13日复旦大学信息科学与工程学院6内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院7数据及操作表示线性结构线性结构是多种数据类型的抽象表示。直观上的线性结构包括：字符串，链表等数据结构。但事实上，线性结构维护的是多个对象间的一个全序关系，而这样一种全序关系是广泛存在的。全序关系的维护是协同环境下一致性维护的基础。树型结构一些主流的文档类型需要树型结构的表示。通过XML可以支持基于关系的操作，是Web应用的需求。2019年9月13日复旦大学信息科学与工程学院8一致性模型因果关系维护（Causalitypreservation）：所有操作的执行顺序都按照它们之间的因果关系。对于任意的两个操作O1和O2，如果O1→O2，则在所有的站点，操作O1都在操作O2之前执行。一致性维护（Convergence）：当相同的操作在所有的站点都执行完成之后，所有的数据副本保持一致。意愿维护（Intentionpreservation）：任何一个操作在任何站点的执行效果都保持和它产生站点一致。2019年9月13日复旦大学信息科学与工程学院9内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院10回溯思想2019年9月13日复旦大学信息科学与工程学院11线性结构的回溯过程2019年9月13日复旦大学信息科学与工程学院12线性结构的回溯过程对难题的解决操作转换方法中TP2条件维护的困难dOPT难题假设几个插入操作都是面向相同的位置，操作之间满足因果顺序或者是并发的。仅仅依靠强制规定操作间的优先级是无法保证结果的收敛性的。False-tie难题假设两个并发的插入操作可能会因为在它们之间一个并发的删除操作，而丢失它们之间的左右位置关系，并且可能得到一个相反的结果。证明过程2个操作N个操作2019年9月13日复旦大学信息科学与工程学院13树型结构的回溯过程2019年9月13日复旦大学信息科学与工程学院14树型结构的回溯过程已有方法的不足操作转换方法（OperationTransformation）方法无法支持关系操作。基于锁和序列化的方法无法满足操作的响应时间和自由度。证明过程2个操作N个操作2019年9月13日复旦大学信息科学与工程学院15内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院16一致性维护的相关问题操作的历史队列通过状态向量表，精简操作的历史队列Undo操作支持通过在回溯过程添加计数器，是回溯过程可以考虑Undo操作支持单站点并发操作的时间戳模型通过分离考虑操作间关系和操作的执行状态，引入两个时间戳，支持操作的并发执行。事务操作的支持2019年9月13日复旦大学信息科学与工程学院17事务操作的支持2019年9月13日复旦大学信息科学与工程学院18内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望2019年9月13日复旦大学信息科学与工程学院19线性结构效率分析线性结构优化，通过调整数据结构，可以优化计数效率平摊效率插入操作的开销可以表示为O(h×logn+logn+d×h+h+d+m)，删除操作的开销为O(h×logn+logn+d×h+h+d)其中h为历史队列长度，n为文档字符数，d为针对一个节点的操作数2019年9月13日复旦大学信息科学与工程学院20树型结构效率分析2019年9月13日复旦大学信息科学与工程学院21原型系统2019年9月13日复旦大学信息科学与工程学院22内容概要背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结2019年9月13日复旦大学信息科学与工程学院23总结本文的工作基于状态转换的一致性维护方法一致性维护的四个相关问题算法的理论分析和实验CoAutoCAD演示系统进一步的工作关系数据库的协同化支持动态性的加入、退出进一步改善操作执行的并发性处理用户意愿的矛盾2019年9月13日复旦大学信息科学与工程学院24攻读硕士学位期间的科研工作读硕士期间已发表和已录用的论文顾宁，杨江明，张琦炜.协同组编辑中基于地址空间转换的一致性维护方法.计算机学报，第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页。2019年9月13日复旦大学信息科学与工程学院25攻读硕士学位期间的科研工作读硕士期间已发表和已录用的论文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.2019年9月13日复旦大学信息科学与工程学院26攻读硕士学位期间的科研工作专利及软件著作权(专利)顾宁、张世超、徐寅俊、杨江明.一种规范驱动的网格工