（时隔半年多总算有话题写了orz
在操作转换算法中，我们知道，CC1-CC6共6个条件为基于上下文的OT系统提出了一组完善的基本需求。以CP1, CP2为代表的属性和前置条件则为操作转换控制算法和转换函数的划分提供了理论支持，我们可以依照CP1-2为两者分配不同的责任。对于CP1和PC-CP1的理解较为直接，我们可以基于[2][4]等设计完善一系列支持字符串的转换函数。但CP2本身，以及打破CP2的前提条件以解决CP2问题的相关表述则较难理解且易出错。本文将尝试通过实例对CP2问题进行一些讨论，讨论时均假定OT系统存储原始编辑操作，不使用MRCV等缓存机制。
在[1]中，CP2被定义为 给定三个上下文相等的操作,$O_a, O_b, O_c$.若$O'_b = IT(O_b, O_c), O'_c = IT(O_c, O_b)$,则
$$
IT(IT(O_a, O_b), O'_c) = IT(IT(O_a. O_c),O'_b).
$$
初看CP2，我们可能会认为CP2只是三个操作层面上的CP1的扩展。而在解决CP2问题时，作者在[2]的7.2节又提出要有一个总的原始操作关系(total ordering of original operations)......COT控制操作进行转换时要对CD内全部操作依照这一前后关系进行排序......由中央服务器进行的操作广播顺序可以直接用于转换和排序过程。此时，我们可能会想，是否是在服务端设置一个线性广播编辑操作的逻辑（不广播给操作发出者）即可解决该问题。
但事情往往没有如此简单，我们需要更准确地理解"total ordering"的重要性。实际上，CP2的存在对应一类3站点或以上才会出现的场景，[3]在2.3节就给出了一个比较好的例子。在下图中，$O_a, O_b, O_c$并发产生，且站点1在执行$O_a$后先收到$O_b$后收到$O_c$。转换$O_c$时，先让$O_c$ $O_b$针对$O_a$进行转换，再让$O'_c$对$O'_b$进行转换。而站点2则相反，先让$O_c$ $O_a$针对$O_b$进行转换，再转换$O'_c$ $O'_a$.
直接看到这一场景，我们可能并不能理解这一问题的破坏性。实际上，许多场景下，上述转换过程也并不会导致一致性问题。例如，假设$O_a, O_b, O_c$分别是在1, 5, 10位置各插入长度为2的不同的字符串，那么转换后 $O_b, O_c$ 插入位置分别向后移动，不会出现一致性问题。
但是，在下方场景中，如此转换将产生错误。我们令$O_a = Delete([3, 6))$，即删除3, 4, 5三个字符，$O_b = Insert(5, "12")$ 即在位置5插入长度为2的字符串，$O_c = Insert(3, "ab")$.
在设计字符串转换函数时，上下文相等的情况下，我们往往会在插入操作针对删除操作进行转换时有这样的逻辑：“若插入位置包含于删除区间，则新的插入位置为删除区间左边界”。那么我们可以得到
$$O_c (a) = Insert(3, "12"), O_b(a) = Insert(3, "ab")$$
$$O_c (b) = Insert(7, "12")$$
我们可以观察到，$O_c$先针对$O_b$进行转换将导致插入位置右移，$O_c$插入的内容无论如何都在$O_b$右侧，而先针对$O_a$转换的话则会使$O_c${$a$} , $O_b${$a$}的插入位置相同。针对插入位置相同的两个插入操作的转换比较有趣，我们此时在转换时由于没有之前的信息，是无法判断应当谁在更前方（左侧）的。在Eyja-OT的实现中，插入位置相同的转换判断，是基于发出编辑操作的站点之间谁是参与协作时间更长的用户进行固定的，而与插入操作之前的转换过程无关。也就是说，由于插入操作针对删除操作转换时，信息出现了损失，导致后续转换会出现一致性问题。
我们可以看到，站点1中$O_c$与$O_a$在原始上下文状态下进行转换，站点2中$O_c$与$O_a$却是在含有$O_b$的上下文中进行转换的，明显违背了[2]中提到的PC-CP2条件。
我们可以再利用[3]的相关内容进行理解。[3]在定义6和定理1中给出了关于CP2更形式化的判断。在刚才的例子中，假设$O_a, O_b, O_c$分别具有全局顺序0, 1, 2. 则$C(O_a) \stackrel{\Rightarrow}{=} C(O_b)$ 且$C(O_a) \stackrel{\Rightarrow}{=} C(O_c)$. 注意由于$O_a$的存在，$O_b, O_c$之前应当是没有这一关系的。因此，若按照刚才例子中的过程进行转换，必然是违背[3]的定理2的。
[2]已经告诉我们，在转换函数层面解决CP2是比较困难的。毕竟转换时有可能会有信息损失。在控制算法层面解决这一问题时，[3]告诉我们，只要避免上述例子中在不同上下文转换同一对操作即可(CP2 can be avoided if an OT system can avoid transforming the same pair of operations in different contexts)。具体而言，设置有中央服务器的系统实际往往存在一个隐式的全局顺序，即每个站点通过TCP连接给服务端串行传输编辑操作，服务端在全部站点间也是串行化的处理。在这种情况下，可以直接利用服务端处理的顺序作为全局的顺序(total ordering)。这一顺序将在服务端广播编辑操作时传递给各个客户端，因此服务端广播的对象是要包括编辑操作的发出者的。Eyja-OT也是这样做的。[3]的4.2节也提到了设置一个全局顺序分发中心等其他避免CP2问题的方法。
设置全局顺序后，回到刚才例子中，我们可以看到，站点2中$O_c$不能先对$O_b$进行转换，因此要对待转换集合CD进行一个排序操作，即对应[1]的7.1节过程3.1。Eyja-OT在实现时，考虑到每次转换都是两两转换，因此采用从候选转换操作列表中选择最小全局序号操作的做法。
以上便是针对CP2的一些讨论和分析。由于我对基于上下文的操作转换的理解也不能说十分透彻，因此也可能存在着某些理解偏差或错误。不过目前Eyja-OT已具有了一定数量和覆盖率的单元测试用例，能够模拟多客户端进行各种并发编辑操作，相信还是可以应对大部分编辑场景的。
以上
Reference
[1] D. Sun and C. Sun, “Context-based operational transformation in distributed collaborative editing systems,” IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 10, pp. 1454–1470, 2009, doi: 10.1109/TPDS.2008.240.
[2] C. Sun, D. Chen, and X. Jia, “Reversible inclusion and exclusion transformation for string-wise operations in cooperative editing systems,” Proc. 21st Australas. Comput. …, 1998, [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.6793&rep=rep1&type=pdf.
[3] Y. Xu and C. Sun, “Conditions and Patterns for Achieving Convergence in OT-Based Co-Editors,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 3, pp. 695–709, 2016, doi: 10.1109/TPDS.2015.2412938.
[4] C. Sun, D. Chen, X. Jia, Y. Zhang, and Y. Yang, “Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems,” ACM Trans. Comput. Interact., vol. 5, no. 1, pp. 63–108, 1998, doi: 10.1145/274444.274447.