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

二维电子表格是应用最为广泛的计算机应用程序之一,随着大数据和云计算的兴起,对二维电子表格的协同编辑需求也日益增长,而CRDT(无冲突复制数据类型)作为近年来被提出的一致性维护方法,基于它的二维电子表格协同编辑方法在以前的文献中很少被研究.本文提出了一种基于CRDT的同步方法,通过检测操作间的关系,调用相应的冲突消解函数,以实现表格协同文档的一致性维护.本文首先定义了4种操作关系:1)正交冲突关系、一维冲突关系、互斥关系和相容关系;2)提出了一种基于CRDT框架下的冲突消解方案来处理这4种操作关系;3)从理论上分析了本文所提出算法的时间复杂度和空间复杂度;4)通过理论证明和实例研究,验证了该算法的正确性,同时本文还开发了Web端的在线表格协同编辑系统Co-Table,进一步证实了算法的正确性.

基于色彩地址空间转换与多版本策略的复杂位图协同模型与一致性维护算法

调色编辑在现有位图协同模型下存在数据发送量大、编辑灵活性差、操作重叠易冲突、生成版本多、站点存储压力大等问题,针对这些问题提出了一种面向复杂位图的调色协同编辑模型。协同操作仅发送坐标与色彩变化量的协同操作,具有数据量小、多维编辑粒度、位置可重叠等特性;增加了时空关系的四维位图协同架构,只保存已编辑的像素点数据可减少数据存储量;采用空间转换的副本状态控制算法,通过回溯重构历史版本,可以确保协同操作总是在正确的副本状态上执行;根据当前状态与策略配置,动态生成分支版本的算法,可以解决此前模型分支版本过多的问题。最后,基于CCI(causality-preservation,convergence,intention-preservation)模型进行正确性推论,开发协同编辑器原型Co-Pixel,随机生成的操作集设计实验,对照Adobe Lightroom模拟实际编辑行为。结果显示提出的模型可有效减少操作产生冲突,降低一致性维护过程中的算法开销,灵活调整用户执行意图维护工作的结果版本。

基于轨迹标签的无结构P2P副本一致性维护算法

副本的存在是一种提高P2P系统的可扩展性、容错性、可用性和减少查询响应时间的有效手段.随着P2P应用逐渐由只读静态文件共享转换为需要实时更新的读写动态文件交互,副本一致性维护成为确保新业务正确运行的关键.从直接更改消息报文角度出发,提出一种基于节点轨迹标签的无结构P2P副本一致性维护算法,通过在传输消息的报文中添加已接收更新消息的节点轨迹地址链表标签,可以在消息传输源节点进行冗余判断,以减少冗余消息数目.同时,针对直接存储节点地址轨迹标签算法的消息长度随着消息传输轮数和网络度数增加而不断加大的问题,提出一种用Bloomfilter替代地址链表轨迹标签的算法.通过Bloomfilter这种简洁的结构表示地址链表,可以减少添加到报文中的轨迹长度,利用Bloomfilter的“或”运算可以简化传输节点的冗余判断.实验结果表明:节点轨迹标签算法可以极大地降低冗余消息数目,提高P2P系统的可扩展性.副本节点网络连通性越强,消息数目和传输带宽的减少就越明显.该研究可以用到传感器网络等其他自组织网络的一致性维护中.

BOM一致性维护

BOM是企业里不同部门、不同流程间传递数据的基本形式 .由于企业内各部门的需求不一样 ,为满足不同的需求 ,企业内存在众多的 BOM型式 ,这些型式的存在阻碍了企业信息的有效传递 ,并可能导致数据不一致 .文中给出部件关系、部件约束、以及部件配置等基本概念的形式化定义 ,并在此基础上给出 BOM的一种柔性的定义 .该形式化定义可有效地减少 BOM的数量与种类 .虽然此定义以制造业为基础 ,然而只要稍加推广 ,便可适用于其它领域 .最后 ,针对 BOM可能出现不一致的几种情况进行分析 。

基于属性更新的语义缓存一致性维护算法

为解决传统语义缓存一致性维护数据通信流量大、更新速度慢、占用空间多的问题,文中提出了一种新的语义缓存一致性维护算法,通过分析语义缓存段与更新语句的条件谓词以及投影属性的关系,并进行语义裁剪,将更新粒度细化至被更新的属性.理论分析和仿真实验结果表明,该算法能够有效地减少数据通信开销、缓存更新时间和占用空间,提高缓存命中率.

梯次利用电池储能系统一致性维护方法研究

梯次利用电池储能系统与常规储能系统相比,面临更加困难的维护工作,需要研究高效的梯次利用电池储能系统维护方法 ,而维护工作的目的之一就是维护电池间的一致性。动力电池退役后应用于储能系统,相比传统新电池储能电站,电池一致性发散问题更为突出。随机抽取两组某纯电动公交车退役电池模组作为试验样本,测试电池模块剩余容量、欧姆内阻等参数,分析欧姆内阻的不一致性和SOC使用区间的不一致性对容量的影响。经分析,被测试退役电池在循环过程中,欧姆内阻没有明显增大趋势,容量的衰退主要由单体电池容量不一致性导致。然后提出一种基于抽样试验的梯次利用电池储能系统维护关键指标确定方法 ,并通过试验证明了该方法的有效性。通过数据分析,抽样电池模块在后期循环中,欧姆内阻一致性没有太大变化,但是SOC使用区间变化较大,尤其是高端SOC区间容量利用率随着循环次数的增加逐渐降低,影响了电池模块的可用容量,是维护中要重点关注的部分。

协同组编辑中基于地址空间转换的一致性维护方法

组编辑中的一致性维护问题在CSCW中是一个重要的技术挑战.文章介绍了一个基于地址空间转换的方法.对于并发操作,地址空间转换方法将文档的地址空间回溯到操作产生时的状态,操作可以直接在这个地址空间下得到执行.与操作转换方法相比,地址空间转换方法仅仅需要决定新操作的位置,避免了操作转换过程中操作间相对位置信息的丢失,不仅可以满足CCI模型,而且可以对Undo操作提供更好的支持.通过证明每个站点字符节点间维持一致的顺序,对应字符节点拥有相同的标记,文中给出了算法对于一致性维护的证明.同时,操作执行的平摊代价可以优化到O(logn).

PATCOM:基于分割树的无结构P2P系统一致性维护方法

无结构P2P技术逐渐被应用在新型的协同计算系统中.这些新型业务支持数据的动态更新,不仅要求副本数据的强一致性,而且要求更新数据的快速传播.高效的一致性维护方法是保证新业务顺利开展的基础.在比较分析现有的P2P系统一致性维护方法的基础上,针对无结构P2P系统,提出了一种基于分割树的一致性维护方法——PATCOM.PATCOM使用Chord协议作为组管理协议,通过不断分割由副本节点组成的Chord环,动态地建立更新消息传播树(Update Message Propagation Tree,UMPT).论文进一步从理论上分析了UMPT的平均高度、PATCOM的性能、容错能力以及算法开销,并和基于Gossip的一致性维护方法进行了比较.理论分析和仿真实验结果表明:PATCOM不仅能够快速地维护P2P系统的强一致性,而且产生的冗余更新消息少.

求解过程中约束一致性维护的多层次策略研究

约束满足问题广泛出现于人工智能领域．在问题求解过程中保持局部约束一致性以缩小问题搜索空间是十分必要的．过去研究者对约束一致性算法的研究仅着眼于改进单个约束关系的维护．该文立足于更高点，提出从求解层次、维护层次和约束层次优化约束一致性维护的原则及其相应策略，算法ＭＡＣ－Ｈ和ＡＣ－Ｉ＋进一步减少了约束一致性维护的总代价，并克服了原有算法空间复杂度大的缺点．文中以两个典型的约束满足问题：Ｎ－皇后问题和斑马难题为分析和测试的例子，证实了这些原则和策略的有效性．

复制式协同图形编辑环境中复合Undo操作语义一致性维护研究

复制式架构下的二维CAD协同图形编辑环境中,用户界面所发出的Undo操作从语义上讲是针对复合操作本身的,但传统的一致性维护算法是基于原子操作的,对Undo操作的支持也是以原子操作为单位的,这样就会导致复合Undo操作的语义不一致性问题。分析了CAD图形编辑环境中复合操作的类型及Undo操作的执行前提,讨论了Undo操作存在的情况下的冲突定义,提出了基于版本分裂机制的冲突解决策略,并描述了复合Undo操作在本地和远程站点的执行流程及主要算法。最后通过实例分析证明了该方法的有效性。

基于图形对象的一致性维护问题的研究

针对实时协同图形编辑系统中一致性维护关键问题,提出了一种基于图形对象的并发控制算法。该算法扩展了面向文本编辑的分布式操作转换dOPT算法,满足图形对象属性级上数据一致性维护,同时通过预定义图形对象间的关联关系和位置属性约束规则,进行操作语义维护管理,使得实时协同图形编辑系统的一致性维护更为有效和完备。

分布式仿真多分辨率建模方法及一致性维护

在分布式仿真中,同一实体的多个分辨率模型并发以及不同实体的各个分辨率模型之间的交互会导致数据表现不一致的问题。在分析现有多分辨率建模方法的基础上,提出了适应分布式仿真环境的不同分辨率模型的树状结构建模方法,其主要由聚合级实体模型和平台级实体模型组成。为解决树状结构建模方法中不同分辨率模型的数据表现不一致问题,将不同分辨率模型间的交互看成分布式数据库中的事务,由此提出了一个嵌套两段式提交协议算法来有效解决不同分辨率模型的一致性维护问题。

多粒度协同下文档一致性维护技术

针对移动网络环境下网络信号不稳定的特点,采用多协同粒度的方式,根据网络状态自主选择协同粒度以适应网络状态.为了支持该协同模式下共享文档的一致性维护,提高算法执行效率,将线性文档映射为树型结构文档模型;增加了发送缓冲区及接收缓冲区,在操作发送之前进行合并捆绑处理,在操作接收之后进行分解处理;通过改进地址空间转换算法,以适应新的模型空间.最后在Android平台上基于开源文本编辑工具包UEditor开发支持多粒度协同的原型系统Co-UEditor,证明了文中方法的有效性.

树型模型中进化设计的一致性维护技术的研究

基于文本操作转换算法已经广泛的应用于协同应用中,但是之前基于文本编辑的协同研究大部分都是基于文本的插入,删除操作,而且研究的对象大多为线性的文档模型,对于新的文档模型和新的操作之前的协同算法已经不适应.本文对基于树型文档模型的遗传操作(包括交叉操作和变异操作)进行了一致性维护研究.对比分析了之前多种协同设计方案的优劣,建立了基于树型文档模型,描述了遗传操作实现的过程,设计和冲突检测和冲突消解算法,提出了一致性维护的流程.最后模拟了协同编辑的场景,并把算法应用于协同编辑,从理论上证明了算法的收敛性和方案的正确性.

C^4ISR体系结构设计工具的产品一致性维护方法

产品一致性维护是确保C4ISR系统体系结构设计正确的重要手段。分析了产品一致性维护的原因,主要是由于体系结构产品之间在描述内容上的密切联系、相互依赖。对产品之间的各种关联关系进行系统地总结,分成显式关联和隐式关联两大类,提出了在C4ISR系统体系结构设计工具中对各类关联关系进行一致性维护的时机、策略和方法,并在自主开发的C4ISR系统体系结构设计环境中实现。

产品多学科协同设计中的一致性维护方法

针对产品多学科协同设计的多域性、多视图性和动态性等特点,研究了多学科视图模型间的关联和协调方法,提出了一种融合功能、行为和结构等的多学科约束-关系网络模型,定义了结构关系集和语义关系集,通过综合应用关系、约束、语义推理及项目管理等多种途径和方法进行了多学科视图模型间的静态和动态协调,进而实现了多学科视图模型间的一致性维护,并以减速器为例进行了分析和说明。

数据网格中复制式数据的一致性维护方法

由于网格环境动态性的特点,网格延迟的不稳定等问题会严重影响数据的可获得性.针对这个问题,采用复制式的数据模型来给予解决.通过在数据网格中维护多个数据副本,用户可以选择其中任意一个进行访问修改.通过将网格服务与数据分离,将数据模型化为线性数据和树型数据,可以支持用户对网格数据的实时修改,并且可以维持多个数据副本的一致性.提出了一个新的时间戳模型,可以支持一个数据副本上的并发操作.本方法是一个无锁的算法,可以满足网格环境下数据的RIC属性.

实时图编辑中参照操作语义一致性维护

在实时协同系统中,传统的语义维护主要是针对文本编辑器中基于字符操作的一致性维护。在这种编辑环境下,字符与字符之间虽然具有前后继关系,但在属性上没有参照或者依赖关系。然而在图形编辑领域,在操作执行过程中,常通过捕获方式建立对象与对象之间的参照关系。针对这种参照关系的维持,目前实时协同中尚未有相关的研究,因此提出了CRSCM(create relation semantic consistency maintenance)语义一致性维护策略。该策略首先根据参照操作的语义信息,构建参照实体与目标实体之间的依赖关系图DRG(dependency relation graph)结构;然后通过远程操作重新获取被捕捉对象属性、并发操作执行更新转换的策略,从而实现了参照操作与其他并发操作的语义维持,并在一定程度上有效解决了协同图编辑中的一致性问题。

MANET中基于簇的缓存一致性维护策略

协作缓存在移动自组织网络中得到了充分的应用和部署.提出了一种基于簇的一致性维护策略CCS(cluster-based consistency scheme).在CCS中,相邻的节点组成一个簇.每个簇中挑选一个能量较高、较稳定的节点作为簇头,而簇中的其他节点与簇头节点最多相距两跳.簇头节点利用基于DHT(distributed Hash table,分布式哈希表)的Chord协议作为组管理协议,即簇头节点组戍一个Chord环.通过动态地在Chord环上建立更新树传播更新内容.这样,更新数据在不同的簇之间是通过更新树传播的,而在簇内是通过MAC层的广播传播的.仿真实验结果表明,与基于流言传播的缓存一致性维护策略相比,CCS具有开销小、成功率高和传播快的特点.

支持操作续传的网络三阶段一致性维护研究

针对网络潜在的不稳定现象,提出支持断网续传的网络三阶段一致性维护算法,我们简称为ORT算法.该算法将网络状态划分为断网前、断网后、联网后三阶段,在之前的支持两站点协同的移动网络协同副本一致性维护算法基础上,引入服务器,实现多用户协同工作.ORT算法配置在服务器端,断网前收发操作并定时更新cursor值,断网后根据站点id和操作net值将操作保存在指定缓冲区,联网后通过三个步骤的处理,查找漏发和丢失操作,并广播到对应站点执行,最终生成一致性副本.为了优化查询、同步效率,服务器端选用树形结构存储各协作站点的历史操作序列,并将压缩策略进行适当更改引用到本算法中.本文最后通过Co-Editor协同编辑原型系统实现证明策略的有效性和正确性.