二维表格实时协同编辑系统的一致性维护  

Research on Consistency Maintenance of Real-time Collaborative 2D Table Editing Systems

作　　者：魏赟[1] 宗旭 高丽萍[1,2] WEI Yun;ZONG Xu;GAO Liping(School of Optical Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China;Shanghai Key Laboratory of Data Science,Fudan University,Shanghai 200093,China)

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093 [2]复旦大学上海数据科学重点实验室,上海200093

出　　处：《小型微型计算机系统》2024年第2期351-358,共8页Journal of Chinese Computer Systems

基　　金：国家重点研发计划项目(2018YFB1700902)资助。

摘　　要：二维电子表格是应用最为广泛的计算机应用程序之一,随着大数据和云计算的兴起,对二维电子表格的协同编辑需求也日益增长,而CRDT(无冲突复制数据类型)作为近年来被提出的一致性维护方法,基于它的二维电子表格协同编辑方法在以前的文献中很少被研究.本文提出了一种基于CRDT的同步方法,通过检测操作间的关系,调用相应的冲突消解函数,以实现表格协同文档的一致性维护.本文首先定义了4种操作关系:1)正交冲突关系、一维冲突关系、互斥关系和相容关系;2)提出了一种基于CRDT框架下的冲突消解方案来处理这4种操作关系;3)从理论上分析了本文所提出算法的时间复杂度和空间复杂度;4)通过理论证明和实例研究,验证了该算法的正确性,同时本文还开发了Web端的在线表格协同编辑系统Co-Table,进一步证实了算法的正确性.2D spreadsheet is one of the most widely used computer application,with the rise of big data and cloud computing,collaborative editing of 2D spreadsheet demand is also growing,and CRDT(Conflict-free Replicated Data Type)as consistency maintenance methods have been proposed in recent years,collaborative editing method based on the 2D spreadsheet is rarely investigated in the previous literatures.In this paper,a CRDT-based synchronization method is proposed.By detecting the relationship between operations and calling the corresponding conflict resolution function to achieve the consistency maintenance of table.Firstly,four operational relations are defined:orthogonal conflict relation,1D conflict relation,mutual exclusive relation and compatible relation.Secondly,a conflict resolution scheme under the CRDT framework is presented to deal with these four operational relations.Thirdly,the time complexity and space complexity of the proposed algorithm are analyzed in theory.Fourthly,the correctness of the algorithm is verified through the case study of Table collaboration.Meanwhile,the paper also develops the Co-table,an online Table collaboration editing system under the Web platform,which further confirms the feasibility and effectiveness of the algorithm.

关 键 词：表格协同 CRDT 一致性维护 冲突消解 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]