Operational Transformations

• OTとも

概要

• 文字列abcのページがある
• 以下2つのオペレーションが平行に行われる
  • O1 = Insert[0, "x"]
  • O2 = Delete[2, "c"]
• O1 → O2:
  • まずO1を適用するとxabc
  • 1文字のInsertが一度されたので位置パラメータが1
  • 次にO2を適用する際に、O2をO1に対して変換しO2' = Delete[2+位置パラメータ, "c"]を得る
  • O2’を適用しxab
• O2 → O1:
  • まずO2を適用するとab
  • 次にO1を適用しxab

アプリケーション もともと共同編集のために生まれた技術

• Apache Wave(Google Wave)
  • https://www.usenix.org/conference/lisa-09/google-wave
• Google Docs

参考文献

• 元論文? : https://dl.acm.org/doi/10.1145/289444.289469
• https://srijancse.medium.com/operational-transformation-the-real-time-collaborative-editing-algorithm-bf8756683f66
• https://srijancse.medium.com/how-real-time-collaborative-editing-work-operational-transformation-ac4902d75682
• https://dl.acm.org/doi/10.1145/2145204.2145411
  • 2Dに拡張したらしい。未読。(kekeho)
• https://hackernoon.com/analysing-different-operational-transformation-algorithms-for-collaborative-editing-60fcc49ef24b
  • いろんなOTのアルゴリズムを紹介している。未読。(kekeho)
• Google Drive Blog: What’s different about the new Google Docs: Working together, even apart
• Google Drive Blog: What’s different about the new Google Docs: Conflict resolution
• https://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447