基于树形结构文档的协同编辑算法

实时协同编辑系统是一类重要的CSCW应用系统,而一致性维护是设计和实现此类系统最具挑战性的一个难题。本文首先扩展CCI模型为CCIC模型,然后把协同编辑的文档结构从线性结构扩展为树形结构,并给出了相应的tree-GOT2算法。treeGOT2算法的操作变换次数比基于线性结构文档的协同算法大量减少,操作粒度也更加灵活,从而操作变换更加有效,体现了现实的优越性。     

实时协同文本编辑系统中共享文档的一致性维护

在分布式实时协同编辑系统中共享文档被复制到一组协作参与者处,如何维护共享文档的一致性成了一个重大挑战。本文在借鉴以往研究经验的基础上,提出了一种新的一致性维护算法FOPT。文中给出了该算法的详细描述并结合实际例子做了分析。     

协同编辑中维护操作意愿的文档标注方法*

在实时协同编辑系统中,操作意愿一致性维护是国际上提出的新概念,是协同系统一致性维护的重要方面.文档标注文法通过对共享文档进行恰当标注,屏蔽并发操作对共享文档造成的影响,使得操作在任意协作点上执行时的环境与操作产生的环境一致,从而有效地维护操作意愿一致性.结合实际应用中的具体操作,重点论述文档标注方法以及相应的控制算法.     

协同编辑中维护操作意愿的文档标注方法

在实时协同编辑系统中,操作意愿一致性维护是国际上提出的新概念,是协同系统一致性维护的重要方面.文档标注文法通过对共享文档进行恰当标注,屏蔽并发操作对共享文档造成的影响,使得操作在任意协作点上执行时的环境与操作产生的环境一致,从而有效地维护操作意愿一致性.结合实际应用中的具体操作,重点论述文档标注方法以及相应的控制算法.     

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

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

基于树型结构的共享文档副本的语义一致性维护

锁操作在实时协同编著系统中用于共享文档副本的语义一致性维护.针对已有线性结构文档中锁操作转换算法效率低下的问题,对文档采用树型结构的表示方法,在文档的不同层级引入可选锁机制,并提出一个新的锁操作转换算法TreeLock_GOTO,大大提高了锁操作转换算法的执行效率.     

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

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

带有度约束的最小耗费生成树的分支限界算法

最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。     

一种基于知识点结构的分布式协同学习一致性模型分析

现代远程教育是基于互联网和终端实现教学活动,协同学习是提高远程学习效能感的重要方式,需要深入研究基于协同学习语义的一致性维护、协同感知等关键技术,以达到足够高效的、自然的互动化及个性化学习。提出一种远程教育特点下协同学习的一致性模型及算法分析,在此模型基础上,形成基于知识点结构的特有的操作转换算法来保持一致性。     

一种测控通信平台的动态负载平衡服务研究

为了提高基于UDP协议的测控通信平台的稳定性、实时性和数据处理能力,建立了动态负载平衡模型,提出了加权负载因子负载平衡算法.该算法利用CPU的使用率、当前的活动会话数、内存的使用率和剩余任务数来衡量服务器的负载,计算任务队列的剩余任务耗费值,并以此确定服务器的负载状态;进一步说明了负载平衡频率和负载平衡粒度控制策略,通过剩余任务耗费值的阈值、阈长和主辅关系的解除时机两个方面控制负载平衡频率,通过任务迁移量来控制负载平衡粒度.最后通过实验证明了该算法的有效性.     

基于预测机制的MAS协商通信模型

网络代价直接影响MAS通信性能,特别是在服务器过载情况下影响更为明显.为减少网络通信代价、减轻服务器负载,引入预测机制,提出一种根据网络代价、服务器负载的预测结果,动态选择agent远程通信或MA迁移方式的协商通信模型MRCM,模型中引入黑板结构,实现预测结果在MAS系统中的共享,增强预测成功率、准确率.实验表明该方法对网络代价、服务器负载预测近似准确,能有效地降低通信开销.     

Efficient and scalable continuous skyline monitoring in two-tier streaming settings

Two-tier streaming settings are a typical dynamic environment where continuous skylines represent an important semantic indicator for multiple attributes. To monitor skylines over the dynamic data in such settings, one needs to continuously update the skyline query results in order to reflect the new data values. This paper tackles the problem of continuous skyline monitoring on a central query server over dynamic data from multiple data sites. Simply sending the updates of tuple values to the server is cost-prohibitive. Therefore, we propose an approach that allows the central server to collaborate with the data sites to monitor the possible skyline changes. By doing so, the processing load is distributed over all the data sites instead of only on the central server. Furthermore, this collaborative approach minimizes the bandwidth consumption between the server and the data sites, which is often critical in a widely distributed environment such as a wide-area sensor network. We give theoretical upper bounds for the computation costs and communication costs of the proposed collaborative approach. We also conduct extensive experiments on both synthetic and real data sets. The experimental results demonstrate that our collaborative approach is efficient, scalable and well-balanced in terms of communication costs and computation costs.     

An efficient partitioning algorithm for distributed virtualenvironment systems

Distributed virtual environment (DVE) systems model and simulate the activities of thousands of entities interacting in a virtual world over a wide area network. Possible applications for DVE systems are multiplayer video games, military and industrial trainings, and collaborative engineering. In general, a DVE system is composed of many servers and each server is responsible to manage multiple clients who want to participate in the virtual world. Each server receives updates from different clients (such as the current position and orientation of each client) and then delivers this information to other clients in the virtual world. The server also needs to perform other tasks, such as object collision detection and synchronization control. A large scale DVE system needs to support many clients and this imposes a heavy requirement on networking resources and computational resources. Therefore, how to meet the growing requirement of bandwidth and computational resources is one of the major challenges in designing a scalable and cost-effective DVE system. In this paper, we propose an efficient partitioning algorithm that addresses the scalability issue of designing a large scale DVE system. The main idea is to dynamically divide the virtual world into different partitions and then efficiently assign these partitions to different servers. This way, each server will process approximately the same amount of workload. Another objective of the partitioning algorithm is to reduce the server-to-server communication overhead. The theoretical foundation of our dynamic partitioning algorithm is based on the linear optimization principle. We also illustrate how one can parallelize the proposed partitioning algorithm so that it can efficiently partition a very large scale DVE system. Lastly, experiments are carried out to illustrate the effectiveness of the proposed partitioning algorithm under various settings of the virtual world     

Practical access control management for distributed collaborative editors

The project summarized in this article aims at developing techniques to support access control in Real-Time Distributed Collaborative Editors (RCE). The ever-increasing role of RCE in academic, industry and society comforts the expansion of data sharing and raises growing concerns about controlling access to this data. Indeed, RCE allow for a human–computer–human interaction in a decentralized fashion. Thus, access control for RCE requires a careful design since they need dynamic access changes and low latency access to shared document while maintaining its consistency.In this article, we propose a flexible access control model where the shared document and its authorization policy are replicated in the local memory of each user. To deal with latency and dynamic access changes, we use an optimistic access control technique in such a way that enforcement of authorizations is retroactive. Our model is generic enough to be deployed on the top of the most of existing logging-based collaborative systems. Indeed, it does not entail overheads and it does not affect the convergence of the shared document. We show that naive coordination between updates of both copies can create security holes on the shared document, by permitting illegal modifications or rejecting legal modifications and present our solutions to avoid these problems. Finally, we present a prototype for managing authorizations in collaborative editing work in a decentralized fashion. Thus our model may be deployed easily on mobile devices over P2P networks.     

Optional and responsive fine-grain locking in Internet-based collaborative systems

Locking is a standard technique used in distributed computing and database systems to ensure data integrity by prohibiting concurrent conflicting updates on shared data objects. Internet-based collaborative systems are a special class of distributed applications which support human-to-human interaction and collaboration over the Internet. In this paper, a novel optional and responsive fine-grain locking scheme is proposed for consistency maintenance in Internet-based collaborative editors. In the proposed scheme, locking is made optional in the sense that a user may update any part of the document without necessarily requesting a lock. In the face of high communication latency in the Internet environment, responsive locking is achieved by granting the permit to the user for updating the data region immediately after issuing a locking request. Moreover, multiple fine-grain locks can be placed on different regions inside a document to allow concurrent and mutually exclusive editing on the same document. Protocols and algorithms for locking conflict resolution and consistency maintenance are devised to address special technical issues involved in optional and responsive fine-grain locking. The proposed locking scheme and supporting techniques were implemented in an Internet-based collaborative editor to demonstrate its feasibility and usability.     

A repartitioning hypergraph model for dynamic load balancing

In parallel adaptive applications, the computational structure of the applications changes over time, leading to load imbalances even though the initial load distributions were balanced. To restore balance and to keep communication volume low in further iterations of the applications, dynamic load balancing (repartitioning) of the changed computational structure is required. Repartitioning differs from static load balancing (partitioning) due to the additional requirement of minimizing migration cost to move data from an existing partition to a new partition. In this paper, we present a novel repartitioning hypergraph model for dynamic load balancing that accounts for both communication volume in the application and migration cost to move data, in order to minimize the overall cost. The use of a hypergraph-based model allows us to accurately model communication costs rather than approximate them with graph-based models. We show that the new model can be realized using hypergraph partitioning with fixed vertices and describe our parallel multilevel implementation within the Zoltan load balancing toolkit. To the best of our knowledge, this is the first implementation for dynamic load balancing based on hypergraph partitioning. To demonstrate the effectiveness of our approach, we conducted experiments on a Linux cluster with 1024 processors. The results show that, in terms of reducing total cost, our new model compares favorably to the graph-based dynamic load balancing approaches, and multilevel approaches improve the repartitioning quality significantly.     

智能电网系统中费控服务的优化调度研究

智能电网系统中,费控指令通过应用服务器集群被下发到前置服务器集群,再通过前置服务器集群被下发到终端,终端接收到指令后将指令下发到特定的智能电表.在这个过程中,应用服务器集群和前置服务器集群的可用资源不对等,导致负载不均衡,影响费控服务执行的效率和成功率;前置服务器集群中前置机与终端的固定匹配方式,容易导致前置服务器集群负载不均衡,延长了费控指令完成时间,降低了费控服务的执行效率.为此深入研究费控指令的下发过程,分析存在的问题和瓶颈,提出了一种基于负载预测和负载均衡的费控服务优化调度模型.该模型首先提出一种基于时间序列的负载预测方法,实现服务器负载的预测;基于预测负载,提出一种费控指令的均衡下发算法,为不同负载的服务器下发合适规模的费控指令,以提高指令下发的效率和成功率;针对前置服务器集群可能出现的负载不均衡,提出一种基于图聚类的终端均衡布局算法.实验结果表明,本文提出的费控服务优化调度模型,均衡了两个集群和终端之间的负载,有效提高了费控指令下发的效率和成功率.     

基于改进混合粒子群算法和匹配理论的无人机电力巡检卸载策略

无人机搭载深度神经网络进行自主电力巡检时由于受到设备本身计算能力、电池容量、深度神经网络计算负载的限制,无法独立处理巡检任务中产生的海量图像数据。为解决该问题,提出了一种基于改进混合粒子群算法和匹配理论的无人机电力巡检卸载策略,该策略将系统成本最小化问题分解为深度神经网络计算任务协同分割和边缘服务器选择两个子问题。针对协同分割子问题,基于深度神经网络计算任务的执行流程提出了一种错时传输方法,通过改进混合粒子群算法求解多无人机任务协同分割层。针对边缘服务器选择子问题,定义无人机与边缘服务器各自偏好函数,根据偏好函数通过匹配理论建立两者间的稳定匹配,得到边缘服务器选择策略。仿真结果表明,与其他卸载策略相比,所提策略能有效降低无人机能耗和计算任务处理时延,促进边缘服务器负载均衡。     

向量空间划分类索引的动态更新代价分析

代价分析是借助代价模型预测和评估空间索引结构的一种有效方法。针对索引的空间划分和数据划分这两种策略,在已有的索引结构基础上建立了向量空间划分类型索引的代价模型,该模型可实现查询以及动态更新的性能评价。以KDB-树系为评估对象,从结点存取次数（NA）值推导计算出页面存取次数（PA）的估计值,并在标准数据分布上对估计值的相关误差率进行了验证。结果表明代价模型的平均相关误差率较低,不超过12%。代价分析的结果有助于对索引结构的动态更新代价的预估和查询的优化。     

面向通信成本优化的联邦学习算法

联邦学习是一种能够保护数据隐私的机器学习设置,然而高昂的通信成本和客户端的异质性问题阻碍了联邦学习的规模化落地。针对这两个问题,提出一种面向通信成本优化的联邦学习算法。首先,服务器接收来自客户端的生成模型并生成模拟数据;然后,服务器利用模拟数据训练全局模型并将其发送给客户端,客户端利用全局模型进行微调后得到最终模型。所提算法仅需要客户端与服务器之间的一轮通信,并且利用微调客户端模型来解决客户端异质性问题。在客户端数量为20个时,在MNIST和CIFAR-10这两个数据集上进行了实验。结果表明,所提算法能够在保证准确率的前提下,在MNIST数据集上将通信的数据量减少至联邦平均（FedAvg）算法的1/10,在CIFAR-10数据集上将通信数据量减少至FedAvg算法的1/100。