【摘要】：有別于傳統(tǒng)分布式系統(tǒng),實時協(xié)同編輯系統(tǒng)強調(diào)自然和諧的人人交互和人機交互,允許不同地點的協(xié)同用戶同時編輯同一共享對象.為了給協(xié)同用戶提供良好的響應(yīng)性,實時協(xié)同編輯系統(tǒng)有必要采用全復(fù)制式體系結(jié)構(gòu),但又給共享對象的一致性維護問題帶來巨大挑戰(zhàn),這一直是協(xié)同計算學(xué)科的研究熱點.近年研究重點逐步從結(jié)果一致性發(fā)展到操作意圖一致性.該文以操作意圖一致性為主線,對支持操作意圖一致性的實時協(xié)同編輯算法進行深入和全面的比較、分析和總結(jié).首先,以Lamport事件偏序關(guān)系為起點,對協(xié)同編輯系統(tǒng)的因果關(guān)系、簡單并發(fā)關(guān)系和偏并發(fā)關(guān)系概念進行整理.同時,給出實時協(xié)同編輯系統(tǒng)中全序關(guān)系的分類,操作的全序和操作對象的全序.在對全序關(guān)系和優(yōu)先級進行剖析的基礎(chǔ)上,闡述了實時協(xié)同編輯系統(tǒng)中的三類一致性模型:CC(Causality-preservation,Convergence)模型、CCI(Causality-preservation,Convergence,Intention-preservation)模型和CA(Causalitypreservation,Admissibility)模型.特別地,文中按照因果一致性、結(jié)果一致性和操作意圖一致性的分類,給出操作意圖一致性的維護路線圖.然后,分別綜述了各類實時協(xié)同編輯算法的研究進展和現(xiàn)狀,包括OT(Operational Transformation)算法、AST(Address Space Transformation)算法和CRDT(Commutative Replicated Data Type)算法.進一步,文中給出了各類操作意圖一致性算法的基本原理和執(zhí)行框架,并基于一個代表性協(xié)同工作場景和算例對典型算法進行詳細解析.接下來,文中從操作意圖一致性、支持操作意圖一致性的典型算法、操作轉(zhuǎn)換函數(shù)和算法時間復(fù)雜度這4個關(guān)鍵方面對實時協(xié)同編輯算法進行歸納和對比.最后對全文小結(jié),并指出為了進一步發(fā)展實時協(xié)同編輯系統(tǒng),未來還需要在優(yōu)先級策略、算法伸縮性、復(fù)雜操作語義類型、粗粒度操作對象以及選擇性撤銷機制等方面深入開展一些研究工作.
[Abstract]:Unlike traditional distributed systems, real-time collaborative editing systems emphasize the natural harmony of human interaction and human-computer interaction, allowing co-users in different locations to edit the same shared object at the same time. In order to provide good response to cooperative users, it is necessary for real-time collaborative editing system to adopt full-replication architecture, but it also brings a great challenge to the consistency maintenance of shared objects, which has been a hot research topic in the field of collaborative computing. In recent years, the focus of research has gradually developed from consistency of results to consistency of operational intent. Based on the consistency of operation intention, this paper makes a deep and comprehensive comparison, analysis and summary of the real-time cooperative editing algorithm which supports the consistency of operation intention. Firstly, the concepts of causality, simple concurrency and partial concurrency relation of cooperative editing system are sorted out with Lamport event partial order relation as the starting point. At the same time, the classification of the total order relation, the total order of the operation and the total order of the operation object in the real-time cooperative editing system are given. Based on the analysis of the total order relation and priority, the, CCI (Causality-preservation,Convergence,Intention-preservation) model and the CA (Causalitypreservation,Admissibility) model of three kinds of consistency models (: CC (Causality-preservation,Convergence) and CA (Causalitypreservation,Admissibility) in real-time collaborative editing system are described. In particular, according to the classification of causality consistency, result consistency and operational intention consistency, the maintenance road map of operational intent consistency is given. Then, the research progress and current situation of all kinds of real-time cooperative editing algorithms, including OT (Operational Transformation) algorithm, AST (Address Space Transformation) algorithm and CRDT (Commutative Replicated Data Type) algorithm, are reviewed respectively. Furthermore, the basic principle and implementation framework of all kinds of algorithms for consistency of operation intention are given, and the typical algorithms are analyzed in detail based on a typical collaborative work scenario and an example. Then, this paper sums up and compares the real-time cooperative editing algorithm from four key aspects: consistency of operation intention, typical algorithm supporting consistency of operation intention, operation conversion function and algorithm time complexity. Finally, it is pointed out that in order to further develop the real-time cooperative editing system, we also need priority strategy, algorithm scalability, and complex operation semantic types in the future. Some researches on coarse-grained operation object and selective revocation mechanism have been carried out.
【作者單位】： 武漢大學(xué)軟件工程國家重點實驗室 武漢大學(xué)計算機學(xué)院 海軍工程大學(xué)計算機工程系
【基金】：國家自然科學(xué)基金(61472289,61502353) 國家重點研發(fā)計劃(2016YFC0106305)資助
【分類號】：TP301.6

【相似文獻】

相關(guān)期刊論文 前10條

1 程彩娟;“八后問題”的算法與程序設(shè)計[J];天津職業(yè)技術(shù)師范學(xué)院學(xué)報;1991年02期

2 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測繪科學(xué)技術(shù)學(xué)報;2009年02期

3 駱雯,孫延明,陳振威,陳錦昌;判斷點與封閉多邊形相對關(guān)系的改進算法[J];機械;1999年03期

4 劉巧玲;張紅英;林茂松;;一種簡單快速的圖像去霧算法[J];計算機應(yīng)用與軟件;2013年07期

5 章郡鋒;吳曉紅;黃曉強;何小海;;基于暗原色先驗去霧的改進算法[J];電視技術(shù);2013年23期

6 周秀玲;郭平;陳寶維;王靜;;幾種計算超體積算法的比較研究[J];計算機工程;2011年03期

7 楊芙清;方裕;陳良華;;計算機編輯系統(tǒng)淺析[J];計算機應(yīng)用與軟件;1988年01期

8 楊芙清;方裕;陳良華;;計算機編輯系統(tǒng)淺析(續(xù))[J];計算機應(yīng)用與軟件;1988年02期

9 張鵬;劉弘;王愛霖;;基于人工蜂群算法的疏散運動仿真[J];計算機工程;2013年07期

10 周順坡;耿昌懷;;一個實用的正文編輯系統(tǒng)[J];計算機研究與發(fā)展;1987年11期

相關(guān)會議論文 前10條

1 尹冀鋒;;一種新的圖象自適應(yīng)增強算法[A];四川省通信學(xué)會一九九二年學(xué)術(shù)年會論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計算機輔助增強、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價值[A];中華醫(yī)學(xué)會第十次全國超聲醫(yī)學(xué)學(xué)術(shù)會議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實現(xiàn)[A];中國光學(xué)學(xué)會2010年光學(xué)大會論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進展——第十三屆全國青年通信學(xué)術(shù)會議論文集（上）[C];2008年

6 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

7 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測算法[A];第六屆和諧人機環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會議（NCMT2010）、第6屆全國人機交互學(xué)術(shù)會議（CHCI2010）、第5屆全國普適計算學(xué)術(shù)會議（PCC2010）論文集[C];2010年

8 吳宜輝;丘律文;李周華;陳國寧;;在分布式圖形協(xié)作編輯系統(tǒng)中解決沖突的一個多版本方法[A];廣西計算機學(xué)會——2004年學(xué)術(shù)年會論文集[C];2004年

9 吳宜輝;丘律文;李周華;陳國寧;;在分布式圖形協(xié)作編輯系統(tǒng)中解決沖突的一個多版本方法[A];廣西計算機學(xué)會2004年學(xué)術(shù)年會論文集[C];2004年

10 楊任爾;陳懇;勵金祥;;基于棱邊方向檢測的運動自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

相關(guān)重要報紙文章 前2條

1 本報實習生　劉霞;天衣無縫的圖片美化技術(shù)[N];科技日報;2007年

2 ;評測公告[N];中國計算機報;2004年

相關(guān)博士學(xué)位論文 前10條

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學(xué);2013年

2 許玉杰;云計算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學(xué);2014年

3 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學(xué);2014年

4 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學(xué);2015年

5 周雷;基于圖結(jié)構(gòu)的目標檢測與分割算法研究[D];上海交通大學(xué);2014年

6 TRAN DANG CONG;粒子群優(yōu)化算法及其在數(shù)據(jù)聚類中的應(yīng)用[D];武漢大學(xué);2015年

7 黃松延;網(wǎng)絡(luò)上的分布式自適應(yīng)估計算法研究[D];浙江大學(xué);2016年

8 李娟;模式分類中若干基本問題的算法研究與應(yīng)用[D];西安電子科技大學(xué);2015年

9 由從哲;子空間聚類分析新算法及應(yīng)用研究[D];江南大學(xué);2017年

10 姚少俊;實時三維內(nèi)容生成算法研究與實現(xiàn)[D];浙江大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 陸進;面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學(xué);2014年

2 李家昌;基于能量約束的超聲圖像自動分割算法[D];華南理工大學(xué);2015年

3 陳堅;基于密度和約束的數(shù)據(jù)流聚類算法研究[D];蘭州大學(xué);2015年

4 高健;基于Zynq7000平臺的去霧算法研究及實現(xiàn)[D];南京理工大學(xué);2015年

5 顧磊;基于Hadoop的聚類算法的數(shù)據(jù)優(yōu)化及其應(yīng)用研究[D];南京信息工程大學(xué);2015年

6 楊燕霞;基于Hadoop平臺的并行關(guān)聯(lián)規(guī)則挖掘算法研究[D];四川師范大學(xué);2015年

7 王羽;基于MapReduce的社區(qū)發(fā)現(xiàn)算法的設(shè)計與實現(xiàn)[D];南京理工大學(xué);2015年

8 許振佳;流式數(shù)據(jù)的并行聚類算法研究[D];曲阜師范大學(xué);2015年

9 李哲f，

本文編號：2270626