協(xié)同組編輯環(huán)境中的數(shù)據(jù)一致性維護(hù)方法課件

協(xié)同組編輯環(huán)境中的數(shù)據(jù)一致性維護(hù)方法學(xué)生：楊江明導(dǎo)師：顧寧教授計算機(jī)與信息技術(shù)系

2023年1月4日協(xié)同組編輯環(huán)境中的數(shù)據(jù)一致性維護(hù)方法學(xué)生：楊江明2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院2內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院2內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院3內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院3內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院4背景及問題的提出協(xié)同組編輯是一個抽象的研究模型傳統(tǒng)的協(xié)同組編輯。GroupSketch（GreenbergandBohnet）、Grove（Ellis,Gibbs,andRein）、ShrEdit（McGuffinandOlson）、DistEdit（KnisterandPrakash）、REDUCE(SubandEllis)單機(jī)軟件的協(xié)同化。ICT(D.LiandR.Li)、CoWord&CoPowerpoint(Xiaetal.)、CoAutoCAD(Guetal.)基于Web2.0的非實時組編輯。CDVE2007(ShenandSun)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院4背景及問題2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院5背景及問題的提出協(xié)同組編輯環(huán)境下問題結(jié)果的一致性問題。如果操作是不可交互的，則不同的操作執(zhí)行順序會導(dǎo)致不同的結(jié)果。操作的依賴性問題。需要保證操作的執(zhí)行條件操作的意愿維護(hù)問題。假設(shè)初始狀態(tài)為“ABC”。在SR1，O3為Insert[“d”,1]，即將”d“插入到位置1(即A和B之間)；而在SR3，O1為Insert[”e“,2]，即將”e“插入到位置2(即B和C之間)。當(dāng)O1

到達(dá)SR1

時，該站點已經(jīng)被操作O3修改成”AdBC“，直接執(zhí)行O1會把字符e插入到字符d和B之間，這顯然是錯誤的。事務(wù)的支持性問題。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院5背景及問題2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院6內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院6內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院7數(shù)據(jù)及操作表示線性結(jié)構(gòu)線性結(jié)構(gòu)是多種數(shù)據(jù)類型的抽象表示。直觀上的線性結(jié)構(gòu)包括：字符串，鏈表等數(shù)據(jù)結(jié)構(gòu)。但事實上，線性結(jié)構(gòu)維護(hù)的是多個對象間的一個全序關(guān)系，而這樣一種全序關(guān)系是廣泛存在的。全序關(guān)系的維護(hù)是協(xié)同環(huán)境下一致性維護(hù)的基礎(chǔ)。樹型結(jié)構(gòu)一些主流的文檔類型需要樹型結(jié)構(gòu)的表示。通過XML可以支持基于關(guān)系的操作，是Web應(yīng)用的需求。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院7數(shù)據(jù)及操作2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院8一致性模型因果關(guān)系維護(hù)（Causalitypreservation）：所有操作的執(zhí)行順序都按照它們之間的因果關(guān)系。對于任意的兩個操作O1和O2，如果O1→O2，則在所有的站點，操作O1都在操作O2之前執(zhí)行。一致性維護(hù)（Convergence）：當(dāng)相同的操作在所有的站點都執(zhí)行完成之后，所有的數(shù)據(jù)副本保持一致。意愿維護(hù)（Intentionpreservation）：任何一個操作在任何站點的執(zhí)行效果都保持和它產(chǎn)生站點一致。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院8一致性模型2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院9內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院9內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院10回溯思想2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院10回溯思想2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院11線性結(jié)構(gòu)的回溯過程2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院11線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院12線性結(jié)構(gòu)的回溯過程對難題的解決操作轉(zhuǎn)換方法中TP2條件維護(hù)的困難dOPT難題假設(shè)幾個插入操作都是面向相同的位置，操作之間滿足因果順序或者是并發(fā)的。僅僅依靠強(qiáng)制規(guī)定操作間的優(yōu)先級是無法保證結(jié)果的收斂性的。False-tie難題假設(shè)兩個并發(fā)的插入操作可能會因為在它們之間一個并發(fā)的刪除操作，而丟失它們之間的左右位置關(guān)系，并且可能得到一個相反的結(jié)果。證明過程2個操作N個操作2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院12線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院13樹型結(jié)構(gòu)的回溯過程2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院13樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院14樹型結(jié)構(gòu)的回溯過程已有方法的不足操作轉(zhuǎn)換方法（OperationTransformation）方法無法支持關(guān)系操作?；阪i和序列化的方法無法滿足操作的響應(yīng)時間和自由度。證明過程2個操作N個操作2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院14樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院15內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院15內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院16一致性維護(hù)的相關(guān)問題操作的歷史隊列通過狀態(tài)向量表，精簡操作的歷史隊列Undo操作支持通過在回溯過程添加計數(shù)器，是回溯過程可以考慮Undo操作支持單站點并發(fā)操作的時間戳模型通過分離考慮操作間關(guān)系和操作的執(zhí)行狀態(tài)，引入兩個時間戳，支持操作的并發(fā)執(zhí)行。事務(wù)操作的支持2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院16一致性維2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院17事務(wù)操作的支持2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院17事務(wù)操作2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院18內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院18內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院19線性結(jié)構(gòu)效率分析線性結(jié)構(gòu)優(yōu)化，通過調(diào)整數(shù)據(jù)結(jié)構(gòu)，可以優(yōu)化計數(shù)效率平攤效率插入操作的開銷可以表示為O(h×logn+logn+d×h+h+d+m)，刪除操作的開銷為O(h×logn+logn+d×h+h+d)其中h為歷史隊列長度，n為文檔字符數(shù)，d為針對一個節(jié)點的操作數(shù)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院19線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院20樹型結(jié)構(gòu)效率分析2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院20樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院21原型系統(tǒng)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院21原型系統(tǒng)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院22內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院22內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院23總結(jié)本文的工作基于狀態(tài)轉(zhuǎn)換的一致性維護(hù)方法一致性維護(hù)的四個相關(guān)問題算法的理論分析和實驗CoAutoCAD演示系統(tǒng)進(jìn)一步的工作關(guān)系數(shù)據(jù)庫的協(xié)同化支持動態(tài)性的加入、退出進(jìn)一步改善操作執(zhí)行的并發(fā)性處理用戶意愿的矛盾2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院23總結(jié)本文2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院24攻讀碩士學(xué)位期間的科研工作讀碩士期間已發(fā)表和已錄用的論文顧寧，楊江明，張琦煒.協(xié)同組編輯中基于地址空間轉(zhuǎn)換的一致性維護(hù)方法.計算機(jī)學(xué)報，第30卷，第5期，2007年5月,763-774頁.楊江明，張琦煒，顧寧.數(shù)據(jù)網(wǎng)格中復(fù)制式數(shù)據(jù)的一致性維護(hù)方法.華中科技大學(xué)學(xué)報（自然科學(xué)版）.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.楊江明，顧寧，吳筱媛.基于地址空間轉(zhuǎn)換方法的Undo操作支持.通信學(xué)報，第27卷，2006年3月，48-56頁。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院24攻讀碩士2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院25攻讀碩士學(xué)位期間的科研工作讀碩士期間已發(fā)表和已錄用的論文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.張琦煒，楊江明，顧寧，楊根興，劉振宇.數(shù)據(jù)網(wǎng)格中的動態(tài)分布式多入口技術(shù).計算機(jī)科學(xué)，第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年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院25攻讀碩士2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院26攻讀碩士學(xué)位期間的科研工作專利及軟件著作權(quán)(專利)顧寧、張世超、徐寅俊、楊江明.一種規(guī)范驅(qū)動的網(wǎng)格工作流描述和驗證方法.專利申請?zhí)枺?00510027785.2,專利申請日：2005年7月15日,公開號：CN1719832(專利)顧寧、楊江明、張琦煒、紹斌.標(biāo)記回溯的一致性維護(hù)方法.專利申請?zhí)枺?00610025690.1,專利申請日：2006年4月13日,公開號：CN1831776(專利)顧寧、楊江明、張琦煒.面向XML的標(biāo)記回溯的一致性維護(hù)方法.專利申請?zhí)枺?00610026459.4,專利申請日：2006年5月11日,公開號：CN1845076(計算機(jī)軟件著作權(quán))軟件名稱：網(wǎng)格工作流管理系統(tǒng)軟件V1.0,編號：軟著登字第039155號,登記號：2005SR07654,首次發(fā)表日期：2005年01月10日(計算機(jī)軟件著作權(quán))軟件名稱：Norm的描述和驗證工具軟件[簡稱：NormTools]V1.0,編號：軟著登字第039165號,登記號：2005SR07664,首次發(fā)表日期：2004年11月10日2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院26攻讀碩士2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院27攻讀碩士學(xué)位期間的科研工作碩士期間參與項目線性結(jié)構(gòu)組操作的理論與算法研究上海市科委基礎(chǔ)研究項目。主持設(shè)計和實現(xiàn)了協(xié)同的Co-AutoCAD原型系統(tǒng)，該系統(tǒng)可以支持多人參與的AutoCAD編輯與設(shè)計，可以在隱藏網(wǎng)絡(luò)延遲的條件下處理用戶間的操作沖突。該原型已完成。在國際頂級會議ACMGroup2005發(fā)表論文一篇。上海高校網(wǎng)格網(wǎng)格數(shù)據(jù)存儲中間件上海市教委重大項目。設(shè)計了基于網(wǎng)格的分布式存儲，支持?jǐn)?shù)據(jù)冗余，容錯，分布式上傳下載，項目已完成。Norm驅(qū)動的虛擬組織關(guān)鍵技術(shù)研究國家自然科學(xué)基金資助項目。參與項目討論和模型設(shè)計。面向信息系統(tǒng)的符號學(xué)技術(shù)研究上海市科委重點項目。參與設(shè)計了基于Norm的網(wǎng)格系統(tǒng)描述工具，該工具已完成。測試知識管理方法與技術(shù)的研究上海市科委重點實驗室人才基金。參與了項目評估與設(shè)計?；贕lobus的網(wǎng)格工作流項目HP公司資助項目。主要負(fù)責(zé)實現(xiàn)其中的工作流引擎服務(wù)部分，項目已完成。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院27攻讀碩士2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院28謝謝！2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院28演講完畢，謝謝觀看！演講完畢，謝謝觀看！協(xié)同組編輯環(huán)境中的數(shù)據(jù)一致性維護(hù)方法學(xué)生：楊江明導(dǎo)師：顧寧教授計算機(jī)與信息技術(shù)系

2023年1月4日協(xié)同組編輯環(huán)境中的數(shù)據(jù)一致性維護(hù)方法學(xué)生：楊江明2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院31內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院2內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院32內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院3內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院33背景及問題的提出協(xié)同組編輯是一個抽象的研究模型傳統(tǒng)的協(xié)同組編輯。GroupSketch（GreenbergandBohnet）、Grove（Ellis,Gibbs,andRein）、ShrEdit（McGuffinandOlson）、DistEdit（KnisterandPrakash）、REDUCE(SubandEllis)單機(jī)軟件的協(xié)同化。ICT(D.LiandR.Li)、CoWord&CoPowerpoint(Xiaetal.)、CoAutoCAD(Guetal.)基于Web2.0的非實時組編輯。CDVE2007(ShenandSun)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院4背景及問題2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院34背景及問題的提出協(xié)同組編輯環(huán)境下問題結(jié)果的一致性問題。如果操作是不可交互的，則不同的操作執(zhí)行順序會導(dǎo)致不同的結(jié)果。操作的依賴性問題。需要保證操作的執(zhí)行條件操作的意愿維護(hù)問題。假設(shè)初始狀態(tài)為“ABC”。在SR1，O3為Insert[“d”,1]，即將”d“插入到位置1(即A和B之間)；而在SR3，O1為Insert[”e“,2]，即將”e“插入到位置2(即B和C之間)。當(dāng)O1

到達(dá)SR1

時，該站點已經(jīng)被操作O3修改成”AdBC“，直接執(zhí)行O1會把字符e插入到字符d和B之間，這顯然是錯誤的。事務(wù)的支持性問題。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院5背景及問題2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院35內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院6內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院36數(shù)據(jù)及操作表示線性結(jié)構(gòu)線性結(jié)構(gòu)是多種數(shù)據(jù)類型的抽象表示。直觀上的線性結(jié)構(gòu)包括：字符串，鏈表等數(shù)據(jù)結(jié)構(gòu)。但事實上，線性結(jié)構(gòu)維護(hù)的是多個對象間的一個全序關(guān)系，而這樣一種全序關(guān)系是廣泛存在的。全序關(guān)系的維護(hù)是協(xié)同環(huán)境下一致性維護(hù)的基礎(chǔ)。樹型結(jié)構(gòu)一些主流的文檔類型需要樹型結(jié)構(gòu)的表示。通過XML可以支持基于關(guān)系的操作，是Web應(yīng)用的需求。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院7數(shù)據(jù)及操作2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院37一致性模型因果關(guān)系維護(hù)（Causalitypreservation）：所有操作的執(zhí)行順序都按照它們之間的因果關(guān)系。對于任意的兩個操作O1和O2，如果O1→O2，則在所有的站點，操作O1都在操作O2之前執(zhí)行。一致性維護(hù)（Convergence）：當(dāng)相同的操作在所有的站點都執(zhí)行完成之后，所有的數(shù)據(jù)副本保持一致。意愿維護(hù)（Intentionpreservation）：任何一個操作在任何站點的執(zhí)行效果都保持和它產(chǎn)生站點一致。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院8一致性模型2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院38內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院9內(nèi)容概要背2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院39回溯思想2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院10回溯思想2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院40線性結(jié)構(gòu)的回溯過程2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院11線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院41線性結(jié)構(gòu)的回溯過程對難題的解決操作轉(zhuǎn)換方法中TP2條件維護(hù)的困難dOPT難題假設(shè)幾個插入操作都是面向相同的位置，操作之間滿足因果順序或者是并發(fā)的。僅僅依靠強(qiáng)制規(guī)定操作間的優(yōu)先級是無法保證結(jié)果的收斂性的。False-tie難題假設(shè)兩個并發(fā)的插入操作可能會因為在它們之間一個并發(fā)的刪除操作，而丟失它們之間的左右位置關(guān)系，并且可能得到一個相反的結(jié)果。證明過程2個操作N個操作2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院12線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院42樹型結(jié)構(gòu)的回溯過程2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院13樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院43樹型結(jié)構(gòu)的回溯過程已有方法的不足操作轉(zhuǎn)換方法（OperationTransformation）方法無法支持關(guān)系操作。基于鎖和序列化的方法無法滿足操作的響應(yīng)時間和自由度。證明過程2個操作N個操作2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院14樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院44內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院15內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院45一致性維護(hù)的相關(guān)問題操作的歷史隊列通過狀態(tài)向量表，精簡操作的歷史隊列Undo操作支持通過在回溯過程添加計數(shù)器，是回溯過程可以考慮Undo操作支持單站點并發(fā)操作的時間戳模型通過分離考慮操作間關(guān)系和操作的執(zhí)行狀態(tài)，引入兩個時間戳，支持操作的并發(fā)執(zhí)行。事務(wù)操作的支持2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院16一致性維2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院46事務(wù)操作的支持2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院17事務(wù)操作2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院47內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)與展望2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院18內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院48線性結(jié)構(gòu)效率分析線性結(jié)構(gòu)優(yōu)化，通過調(diào)整數(shù)據(jù)結(jié)構(gòu)，可以優(yōu)化計數(shù)效率平攤效率插入操作的開銷可以表示為O(h×logn+logn+d×h+h+d+m)，刪除操作的開銷為O(h×logn+logn+d×h+h+d)其中h為歷史隊列長度，n為文檔字符數(shù)，d為針對一個節(jié)點的操作數(shù)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院19線性結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院49樹型結(jié)構(gòu)效率分析2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院20樹型結(jié)構(gòu)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院50原型系統(tǒng)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院21原型系統(tǒng)2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院51內(nèi)容概要背景及問題的提出一致性模型回溯思想與一致性維護(hù)方法一致性維護(hù)的相關(guān)問題效率分析與原型系統(tǒng)總結(jié)2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院22內(nèi)容概要2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院52總結(jié)本文的工作基于狀態(tài)轉(zhuǎn)換的一致性維護(hù)方法一致性維護(hù)的四個相關(guān)問題算法的理論分析和實驗CoAutoCAD演示系統(tǒng)進(jìn)一步的工作關(guān)系數(shù)據(jù)庫的協(xié)同化支持動態(tài)性的加入、退出進(jìn)一步改善操作執(zhí)行的并發(fā)性處理用戶意愿的矛盾2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院23總結(jié)本文2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院53攻讀碩士學(xué)位期間的科研工作讀碩士期間已發(fā)表和已錄用的論文顧寧，楊江明，張琦煒.協(xié)同組編輯中基于地址空間轉(zhuǎn)換的一致性維護(hù)方法.計算機(jī)學(xué)報，第30卷，第5期，2007年5月,763-774頁.楊江明，張琦煒，顧寧.數(shù)據(jù)網(wǎng)格中復(fù)制式數(shù)據(jù)的一致性維護(hù)方法.華中科技大學(xué)學(xué)報（自然科學(xué)版）.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.楊江明，顧寧，吳筱媛.基于地址空間轉(zhuǎn)換方法的Undo操作支持.通信學(xué)報，第27卷，2006年3月，48-56頁。2022年12月25日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院24攻讀碩士2023年1月4日復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院54攻讀碩士學(xué)位期間的科研工作讀碩士期間已發(fā)表和已錄用的論文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.張琦煒，楊江明，顧寧，楊根興，劉振宇.數(shù)據(jù)網(wǎng)格中的動態(tài)分布式多入口技術(shù).計算機(jī)科學(xué)，第32卷，2005年7月增刊A，127-131頁。JiangmingYang,NingGuandXiaoyuanWu.Adocumentmarkbasedonmethodsupportinggroupundo.InInternationalWorkshoponCollaborativeEditingSystems,ACMCSCW’2004,November2004,Chicago,USA.NingGu,JunXu,XiaoyuanWuandJiangmingYang.Asolutiontothesemanticconflictsinthecollaborativeeditingof