[發明專利]大規模協同環境下的協同交互優化方法

無效

• 申請號: 200710045946.X
• 申請日: 2007-09-13
• 公開（公告）號: CN101119365A
• 公開（公告）日: 2008-02-06
• 發明（設計）人: 顧寧;張琦煒;楊江明;朱麟
• 申請（專利權）人: 復旦大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F17/50
• 代理公司: 上海正旦專利代理有限公司
• 代理人: 陸飛;盛志范

技術領域

本發明屬于計算機支持的協同工作技術領域，具體涉及在大規模協同環境下協同交 互優化方法。

背景技術

1.實時組編輯系統

單用戶的文檔編輯系統，如普通的文檔編輯器，在人們生活中已經十分普遍。但近 年來隨著Internet的發展和社會合作的需求，將這些單用戶的編輯系統移植到多用戶的環 境下，允許多個用戶通過計算機網絡同時瀏覽、編輯一個共享數據對象，使之能夠在多用 戶協同工作時發揮重要的作用，這樣的需求也就自然而然地產生了，這種編輯系統稱為組 編輯系統。

實時組編輯系統是組編輯系統中應用最廣泛的一種，其必須滿足實時性、分布式和提 供用戶無限制編輯的特性。現在普遍采用全復制式結構來實現這種系統，也就是說，每個 用戶都有一個文檔數據副本，而且他們被允許并發地、同步地修改這份共享文檔。這里有 三個條件必須被滿足，那就是結果一致、因果一致和用戶意圖一致。結果一致指同一操作 集合在所有站點執行后，這些站點上的文檔狀態一致。因果一致指對于任意兩個操作O_a和 O_b，如果在O_b的初始站點上，O_a在O_b生成前已被生成或執行，則在所有站點上O_a都應早于 O_b被執行。用戶意圖一致指對于任意操作O，其在所有站點上的執行效果都應保持O的原有 意圖，同時O的執行效果不能影響那些與O并發的操作的執行效果。

2.大規模協同環境

盡管目前對實時組編輯的研究已經取得了很大的進展，然而，現有的對實時組編輯的 研究都還主要局限于小組協同(人數小于₁₀)。在更大規模的協同環境中(人數大于₁₀， 甚至成百上千)支持實時組編輯活動會遇到什么樣的特殊問題？ 比如遠程Autocad教學的例子，學習者可以通過編輯修改一份共享AutoCAD文檔數據，實 時地相互交流，不必再局限于白板、Instant?Messenger等通用的協同交互工具，這樣的交 流方式更為直接，往往也更有利于學習者表達自己的觀點和想法。但這種遠程教學學生群 規模龐大，可以認為是大規模協同環境。

3.因果與并發關系檢測

全復制結構下的實時組編輯系統允許用戶并發的編輯修改他們各自的文檔數據副本。 兩個操作具有因果關系指的是一個操作在另一個操作的產生之前已經執行；而兩個操作并 發指的是這兩個操作不存在因果關系。準確識別操作間的因果并發關系是正確維護實時組 編輯一致性的基礎。實時組編輯應用中的因果并發關系判斷主要涉及三方面的問題： 判斷一個操作是否因果就緒：網絡傳輸具有不確定性，操作以它們的生成順序先后發 出，卻未必能按相同的順序到達目標站點。

(2)找出所有之前執行過的與當前正在執行的遠程操作并發的操作。本地站點收到從遠程站 點發過來的這種操作時，首先需要對這種操作作轉換，因為該操作從產生到傳輸完畢，本 地產生了新的操作。如果將該遠程操作直接執行。會導致不一致的情況。那么轉換就意味 著遠程操作要根據本地操作作相應轉換后再執行。

目前比較操作間的相互關系主要手段是比較時間戳。傳統的時間戳是一個N維的向量， 向量的第i個元素記錄的是第i個站點當前已執行操作個數。后來又有人提出直接因果先序 時間戳DCV。

4.DCV時間戳的優點和弊端

定義：直接因果先序關系()：給定兩個任意的操作O_a和O_b，O_a直接因果先序于O_b， 記為O_aO_b，當且僅當(1)O_a→O_b并且(2)不存在一個操作O_c，滿足O_a→O_c且O_c→ O_b。