操作変換

操作変換（英: Operational transformation; OT）は、高度なグループウェア・システムにおいて、各種の協調機能をサポートするための技術である。もともと操作変換は、プレーンテキスト文書の協同編集における整合性保持と並行性制御のために考案された。20年にわたる研究の結果、操作変換の能力と応用は以下を含むものへと拡張された。すなわち、グループ・アンドゥ、ロック、衝突解決、操作通知および圧縮、グループ認識、HTML/XMLおよび木構造文書の編集、協調オフィス生産性向上ツール、アプリケーション共有、協調コンピュータ支援メディアデザインツール、である。近年では、操作変換は、ウェブアプリケーションのGoogle Wave (en) や、その後を継ぐ Google ドキュメントの協調機能の中核技術としても使われている。

歴史

操作変換の先駆けとなったのは、1989年にC. EllisとS. Gibbsが発表したGROVE(GRoup Outtie Viewing Edit)システムである^[1]。数年後には、正確性について多少の課題が認められ、これらの課題を解決するいくつかの提案がなされた^[2] ^[3] ^[4] ^[5] 。その後さらに10年間、専門研究者のコミュニティによる操作変換の継続的な拡張と改善が続けられた。1998年には、協調編集の研究者と操作変換の研究者の間の交流を目的としてSIGCE(An International Special Interest Group on Collaborative Editing)が立ち上げられた。以降、SIGCEは毎年、ACM CSCWやGROUP、ECSCWなどの主だったコンピュータ支援協調作業のカンファレンスと合同で、協調編集に関するワークショップを開催している。

システム・アーキテクチャ

操作変換を利用する協調システムは、インターネットのような高レイテンシ環境において良好な応答性を確保するため、通常、共有文書ストレージ向けの複製アーキテクチャを採用する。共有文書は、各コラボレーティング・サイトのローカルストレージで複製される。編集操作はローカルサイトで直ちに実行でき、その後リモートサイトに伝播させる。リモートの編集操作がローカルサイトへ届くと、通常は変換されたあと実行される。この変換により、アプリケーション依存の整合性尺度を、全てのサイトで達成することを保証する。操作変換は、ロックフリーによるノンブロッキングの特性を備えるため、ローカルの応答時間はネットワーク・レイテンシに影響されない。結果として、操作変換は、ウェブ/インターネット上でのグループ編集といった協調機能の実装に対し、特に適している。

基本

操作変換の基本的なアイデアを、単純なテキスト編集のシナリオを用いて以下で説明する。

"abc"という文字列を含む文書があり、これは二つのコラボレーティング・サイト上に複製されている。ここで、二つの並列操作

O1 = Insert[0, "x"]（0の位置に文字"x"を挿入する）
O2 = Delete[2, "c"]（2の位置にある文字"c"を削除する）

が、コラボレーティング・サイト1および2の二人のユーザによって、それぞれ生成される。ここで、サイト1において、二つの操作がO1, O2の順番で実行されると仮定する。

操作O1を実行すると、文書は"xabc"となる。次に、操作O2を操作O1の後で実行するには、操作O2を O2' = Delete[3, "c"] と変換しなければならない。すなわち、操作O1によって文字"x"が挿入されたことにより、操作O2の位置パラメータを1文字分インクリメントする必要がある。"xabc"に対して操作O2'を実行すると、正しい文字"c"が削除され、文書は"xab"となるだろう。しかし、もし操作O2を変換せずに実行すると、誤って文字"c"ではなく"b"を削除してしまう。

操作変換の基本的なアイデアは、ある編集操作のパラメータを、過去に実行された並列操作の結果に従って変換（あるいは調整）することにある。これにより、変換された操作は正しい結果を実現し、文書の整合性を維持できる。

脚注

^ Ellis, C.A.; Gibbs, S.J. (1989). “Concurrency control in groupware systems”. ACM SIGMOD Record 18 (2): 399–407. doi:10.1145/66926 2007年7月26日閲覧。.
^ Ressel, Matthias and Nitsche-Ruhland, Doris and Gunzenhäuser, Rul (1996). "An integrating, transformation-oriented approach to concurrency control and undo in group editors". CSCW '96: Proceedings of the 1996 ACM conference on Computer supported cooperative work. pp. 288--297.doi:10.1145/240080.240305
^ Chengzheng Sun; Xiaohua Jia ; Yanchun Zhang ; Yun Yang ; David Chen (1998). “Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems”. ACM Trans. Comput.-Hum. Interact. 5 (1): 63–108. doi:10.1145/274444.274447.
^ Nichols, D.A.; Curtis, P.; Dixon, M.; Lamping, J. (1995), “High-latency, low-bandwidth windowing in the Jupiter collaboration system”, Proceedings of the 8th annual ACM symposium on User interface and software technology: 111–120
^ Sun, C.; Ellis, C. (1998). "Operational transformation in real-time group editors: issues, algorithms, and achievements". Proceedings of the 1998 ACM conference on Computer supported cooperative work. ACM Press New York, NY, USA. pp. 59–68.

外部リンク

英語

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[Ellis1989-1] Ellis, C.A.; Gibbs, S.J. (1989). “Concurrency control in groupware systems”. ACM SIGMOD Record 18 (2): 399–407. doi:10.1145/66926 2007年7月26日閲覧。.

[Ressel1996-2] Ressel, Matthias and Nitsche-Ruhland, Doris and Gunzenhäuser, Rul (1996). "An integrating, transformation-oriented approach to concurrency control and undo in group editors". CSCW '96: Proceedings of the 1996 ACM conference on Computer supported cooperative work. pp. 288--297.doi:10.1145/240080.240305

[suntochi1998-3] Chengzheng Sun; Xiaohua Jia ; Yanchun Zhang ; Yun Yang ; David Chen (1998). “Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems”. ACM Trans. Comput.-Hum. Interact. 5 (1): 63–108. doi:10.1145/274444.274447.

[nichols1995-4] Nichols, D.A.; Curtis, P.; Dixon, M.; Lamping, J. (1995), “High-latency, low-bandwidth windowing in the Jupiter collaboration system”, Proceedings of the 8th annual ACM symposium on User interface and software technology: 111–120

[suncscw1998-5] Sun, C.; Ellis, C. (1998). "Operational transformation in real-time group editors: issues, algorithms, and achievements". Proceedings of the 1998 ACM conference on Computer supported cooperative work. ACM Press New York, NY, USA. pp. 59–68.

[1]

[2]

[3]

[4]

[5]