【摘要】：有別于傳統(tǒng)分布式系統(tǒng),實(shí)時(shí)協(xié)同編輯系統(tǒng)強(qiáng)調(diào)自然和諧的人人交互和人機(jī)交互,允許不同地點(diǎn)的協(xié)同用戶(hù)同時(shí)編輯同一共享對(duì)象.為了給協(xié)同用戶(hù)提供良好的響應(yīng)性,實(shí)時(shí)協(xié)同編輯系統(tǒng)有必要采用全復(fù)制式體系結(jié)構(gòu),但又給共享對(duì)象的一致性維護(hù)問(wèn)題帶來(lái)巨大挑戰(zhàn),這一直是協(xié)同計(jì)算學(xué)科的研究熱點(diǎn).近年研究重點(diǎn)逐步從結(jié)果一致性發(fā)展到操作意圖一致性.該文以操作意圖一致性為主線(xiàn),對(duì)支持操作意圖一致性的實(shí)時(shí)協(xié)同編輯算法進(jìn)行深入和全面的比較、分析和總結(jié).首先,以L(fǎng)amport事件偏序關(guān)系為起點(diǎn),對(duì)協(xié)同編輯系統(tǒng)的因果關(guān)系、簡(jiǎn)單并發(fā)關(guān)系和偏并發(fā)關(guān)系概念進(jìn)行整理.同時(shí),給出實(shí)時(shí)協(xié)同編輯系統(tǒng)中全序關(guān)系的分類(lèi),操作的全序和操作對(duì)象的全序.在對(duì)全序關(guān)系和優(yōu)先級(jí)進(jìn)行剖析的基礎(chǔ)上,闡述了實(shí)時(shí)協(xié)同編輯系統(tǒng)中的三類(lèi)一致性模型:CC(Causality-preservation,Convergence)模型、CCI(Causality-preservation,Convergence,Intention-preservation)模型和CA(Causalitypreservation,Admissibility)模型.特別地,文中按照因果一致性、結(jié)果一致性和操作意圖一致性的分類(lèi),給出操作意圖一致性的維護(hù)路線(xiàn)圖.然后,分別綜述了各類(lèi)實(shí)時(shí)協(xié)同編輯算法的研究進(jìn)展和現(xiàn)狀,包括OT(Operational Transformation)算法、AST(Address Space Transformation)算法和CRDT(Commutative Replicated Data Type)算法.進(jìn)一步,文中給出了各類(lèi)操作意圖一致性算法的基本原理和執(zhí)行框架,并基于一個(gè)代表性協(xié)同工作場(chǎng)景和算例對(duì)典型算法進(jìn)行詳細(xì)解析.接下來(lái),文中從操作意圖一致性、支持操作意圖一致性的典型算法、操作轉(zhuǎn)換函數(shù)和算法時(shí)間復(fù)雜度這4個(gè)關(guān)鍵方面對(duì)實(shí)時(shí)協(xié)同編輯算法進(jìn)行歸納和對(duì)比.最后對(duì)全文小結(jié),并指出為了進(jìn)一步發(fā)展實(shí)時(shí)協(xié)同編輯系統(tǒng),未來(lái)還需要在優(yōu)先級(jí)策略、算法伸縮性、復(fù)雜操作語(yǔ)義類(lèi)型、粗粒度操作對(duì)象以及選擇性撤銷(xiāo)機(jī)制等方面深入開(kāi)展一些研究工作.
[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é)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 武漢大學(xué)計(jì)算機(jī)學(xué)院 海軍工程大學(xué)計(jì)算機(jī)工程系
【基金】：國(guó)家自然科學(xué)基金(61472289,61502353) 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFC0106305)資助
【分類(lèi)號(hào)】：TP301.6

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

9 張鵬;劉弘;王愛(ài)霖;;基于人工蜂群算法的疏散運(yùn)動(dòng)仿真[J];計(jì)算機(jī)工程;2013年07期

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

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

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

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

3 謝麗聰;;SVB查詢(xún)改寫(xiě)算法的改進(jìn)[A];第二十一屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2004年

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

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

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

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

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

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

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

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

1 本報(bào)實(shí)習(xí)生　劉霞;天衣無(wú)縫的圖片美化技術(shù)[N];科技日?qǐng)?bào);2007年

2 ;評(píng)測(cè)公告[N];中國(guó)計(jì)算機(jī)報(bào);2004年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9 李哲f，

本文編號(hào)：2270627