Configurable three-way model merging

Software development is a collaborative activity that requires teams of software engineers to cooperate and work in parallel on versions of models. However, model management techniques such as model differencing, merging, and versioning have turned out to be difficult challenges, due to the complexity of operations and graph-like nature of models. Therefore, a well-developed support for model merging process, as well as conflict management, is highly desired. This paper presents a novel process for model merging, called the Epsilon-based Three-way Merging Process (E3MP) process. Model merging is a significant problem where there are different versions of a system model amongst modeler teams. E3MP includes three components implemented into the Epsilon framework. First, modelers can define domain-specific rules that customize the merging process. Second, E3MP enables an automated method for syntactic and semantic conflict detection amongst different versions of the system model. Third, E3MP puts forward a pattern-based approach for conflict resolution. We applied two generic benchmarks to assess conflict detection and resolution capabilities of our approach and carried out an initial scalability evaluation for the model merge with large models and large change sets. The results of our experiments revealed that the proposed process allows generating consistent and semantically correct merged models.     

Maximizing the number of conflict-free aircraft using mixed-integer nonlinear programming

We address the conflict detection and resolution problem in air traffic control, where an aircraft conflict is a loss of separation between aircraft trajectories. Conflict avoidance is crucial to ensure flight safety and remains a challenging traffic control problem. We focus on speed control to separate aircraft and consider two approaches: (i) maximize the number of conflicts resolved and (ii) identify the largest set of conflict-free aircraft. Both problems are modeled using mixed-integer nonlinear programming and a tailored greedy algorithm is proposed for the latter. Computational efficiency is improved through a pre-processing algorithm which attempts to reduce the size of the conflict resolution models by detecting the existence of pairwise potential conflicts. Numerical results are provided after implementing the proposed models and algorithms on benchmark conflict resolution instances. The results highlight the benefits of using the proposed pre-processing step as well as the versatility and the efficiency of the proposed models.     

Knowledge-based system for railway scheduling

In this paper, we describe a Knowledge-Based railway scheduling system (called RSS) for Taiwan Railway Administration's (TRA) railway scheduling operations. In our approach, the scheduling process is divided into two levels: global scheduling and local scheduling. In global scheduling, an initial train diagram is established by the Global Scheduler according to the master scheduling plan without considering conflicts. In local scheduling, scheduling conflicts are repaired by Local Scheduler. An embedded knowledge base provides advice for conflict resolution. Since cycles may exist among a sequence of repairs during the repair process, we also propose a cycle detection and resolution scheme in this paper. Through a graphic user interface, the user can interact with the Automatic Scheduler to solve the large-scale complex train scheduling problem in a cooperative and flexible fashion.     

Distributed conflict resolution among cooperating expert systems

Abstract: Cooperating experts approach attempts to integrate and coordinate the activities of multiple specialised problem solvers that come together to solve complex tasks such as design, medical diagnosis, business management and so on. Due to the different goals, knowledge and viewpoints of agents, conflicts may arise at any phase of the problem-solving process. Managing diverse expertise requires well-organised models of conflict resolution. In this paper, a model for cooperating experts is described which openly supports multi-agent conflict detection and resolution. The model is based on the idea that each agent has its own conflict knowledge which is separated from its domain level knowledge, and each agent has its own conflict resolution knowledge which is not accessible and known by others. Furthermore, there are no globally known conflict resolution strategies. Each agent involved in a conflict chooses a resolution scheme according to its self interest. The model is described by using an example in the domain of office design and it is compared with other systems.     

Conflict resolution in collaborative planning dialogs

In a collaborative planning environment in which the agents are autonomous and heterogeneous, it is inevitable that discrepancies in the agents' beliefs result in conflicts during the planning process. In such cases, it is important that the agents engage in collaborative negotiation to resolve the detected conflicts in order to determine what should constitute their shared plan of actions and shared beliefs. This paper presents a plan-based model for conflict detection and resolution in collaborative planning dialogs. Our model specifies how a collaborative system should detect conflicts that arise between the system and its user during the planning process. If the detected conflicts warrant resolution, our model initiates collaborative negotiation in an attempt to resolve the conflicts in the agent's beliefs. In addition, when multiple conflicts arise, our model identifies and addresses the most effective aspect in its pursuit of conflict resolution. Furthermore, by capturing the collaborative planning process in a recursive Propose–Evaluate–Modify cycle of actions, our model is capable of handling embedded negotiation during conflict resolution.     

移动科研在线中基于冲突解决的数据同步策略

移动科研在线是协同工作环境套件Duckling的应用之一,但由于移动计算环境存在低带宽、长延迟和频繁断接等问题,当多个用户对同一数据进行操作时容易引发冲突,因此冲突处理和数据同步是该应用的关键问题。为此,提出一种基于冲突解决的数据同步策略。给出数据同步的总体框架和策略,分析冲突处理流程,根据冲突发生的场景,结合用户分类和优先级建立消息推送模型。以移动科研在线中的团队通讯录为例在Android平台上进行原型实现,结果显示,该策略可有效节约网络带宽,提高同步效率,具有良好的用户体验。     

Modellierungsunterstützung für die rollenbasierte Delegation in prozessgestützten Informationssystemen

In the paper, an integrated approach for the modeling and enforcement of delegation policies in process-aware information systems is presented. In particular, a delegation extension for process-related role-based access control (RBAC) models is specified. The extension is generic in the sense that it can be used to extend process-aware information systems or process modeling languages with support for process-related RBAC delegation models. Moreover, the detection of delegation-related conflicts is discussed and a set of pre-defined resolution strategies for each potential conflict is provided. Thereby, the design-time and runtime consistency of corresponding RBAC delegation models can be ensured. Based on a formal metamodel, UML2 modeling support for the delegation of roles, tasks, and duties is provided. A corresponding case study evaluates the practical applicability of the approach with real-world business processes. Moreover, the approach is implemented as an extension to the BusinessActivity library and runtime engine.     

分布式目录同步的冲突处理与副本管理研究

随着用户拥有电脑数目的增多,为了维护多机之间数据的一致性,目录同步正成为十分普遍的应用.然而在分布式环境下进行目录同步,因客户机频繁接入网络,造成数据传输延时不可知,并发操作识别需要重新界定,修改冲突也无法采用传统加锁机制处理.为了解决上述问题,提出了MSVerion算法,该算法融合了SVN的冲突发现和Vector Clock的副本管理,能在合并变化文件时快速地发现冲突,减少分布式环境下文件副本管理中需要保存的数据量.同时遵循最终一致性理论,给出了目录同步中3种冲突操作的解决策略.     

网管系统策略冲突解决的结果中存在的问题及检测与解决方法

当前，多种方法被用来解决网管系统中的策略冲突，不同方法有不同的应用范围，因此，通常需要综合应用多种方法来解决策略之间的冲突．各种方法解决策略冲突解决的过程是相对独立的，其策略冲突解决的结果也是相对独立的．在解决策略冲突的过程中，难以考虑到已经存在的策略冲突解决结果．因此。不同的策略冲突解决方法的结果之间可能存在冲突．分析了网管系统中多策略冲突解决方法的结果中可能存在的冲突，提出了检测及解决这些冲突的方法，并给出了实验结果及结论．     

A fundamental approach to model versioning based on graph modifications: from theory to implementation

In model-driven engineering, models are primary artifacts that can evolve heavily during their life cycle. Therefore, versioning of models is a key technique to be offered by integrated development environments for model-driven engineering. In contrast to text-based versioning systems, we present an approach that takes model structures and their changes over time into account. Considering model structures as graphs, we define a fundamental approach where model revisions are considered as graph modifications consisting of delete and insert actions. Two different kinds of conflict detection are presented: (1) the check for operation-based conflicts between different graph modifications, and (2) the check for state-based conflicts on merged graph modifications. For the merging of graph modifications, a two-phase approach is proposed: First, operational conflicts are temporarily resolved by always giving insertion priority over deletion to keep as much information as possible. Thereafter, this tentative merge result is the basis for manual conflict resolution as well as for the application of repair actions that resolve state-based conflicts. If preferred by the user, giving deletion priority over insertion might be one solution. The fundamental concepts are illustrated by versioning scenarios for simplified statecharts. Furthermore, we show an implementation of this fundamental approach to model versioning based on the Eclipse Modeling Framework as technical space.     

Emphasizing conflict resolution versus conflict avoidance during schedule generation

Classical planning systems attempt to solve a planning problem by avoiding possible conflicts before the actions are put on a timeline. This is computationally very expensive and the search for all possible future conflicts may be prohibitive. A conflict resolution approach can check for immediate conflicts and try conflict resolution strategies as each activity is put on a timeline without regard for possible future conflicts. A more practical approach is to use a combination of conflict avoidance and conflict resolution based upon heuristics which limit the amount of search required when either is used. Because humans are not good at solving problems which require complex lookahead, this combined approach, with emphasis on conflict resolution, is what human schedulers actually use when they develop schedules. A system which simulates this human approach to scheduling has been developed at NASA's Goddard Space Flight Center for scheduling satellite activities. This system, which includes the Planning And Resource Reasoning (PARR) shell, allows expert schedulers to specify conflict resolution strategies as well as conflict avoidance strategies to be used during the scheduling process. PARR has been used since May 1987 to schedule the Tracking and Data Relay Satellite System services for the Earth Radiation Budget Satellite. PARR will also be used to schedule platform resources on the Explorer Platform, scheduled for launch in early 1992. This paper describes the advantages of using a combined conflict avoidance and resolution approach in a satellite scheduling system.     

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

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

Applying ontology-based blog to detect information system post-development change requests conflicts

Post-development change requests are user requirements for information systems changes after development. Conflicts might occur as contradictive or inconsistent relationships between requests and existing system design. Detecting conflicts in post-developmenet change requests is an important task during requests management processes. To address this topic, this article proposes an ontology-based blog for automatically discovering conflicts in the extended use-case models of requests from users. This study proposed an information system maintenance process. The proposed approach applies ontologies to represent domain knowledge. A set of rules are used to detect conflicts. This study developed a prototype and invited two companies to evaluate it. Usage feedback opinions about ontology-based blog from two companies indicated the usefulness. The ontology-based blog is a relatively new approach which bridge requirements blogs with a formal and machine interpretable representational model. The automatic conflicts detection capability of the ontology-based blog can reduce the labor cost in requirements analysis phase.     

一种模型重构冲突消解算法

冲突是研究模型重构中的一个重要问题,多数研究将该问题的重点放在冲突检测上,通过对已知冲突的分析,找出冲突消解的手工实现方式.为实现模型重构的自动过程而寻找自动消解冲突的方法是主要研究内容.根据冲突发生的条件将冲突分为3种类型:同一规则的并行使用产生的冲突、对称冲突、非对称冲突.该方法建立在手工分析这3类重构冲突消解的基础上,将重构规则预设为一个规则矩阵,对图转换系统中出现的重构规则进行扫描.扫描结果对照规则矩阵,判断冲突是同一规则还是不同规则的并行使用所产生;分别对这两种情况下的冲突所操作的对象进行分析,根据已有手工消解方法有针对性地进行消解操作.这一算法可以初步实现并行执行的3类冲突的自动消解.     

弱连接网络环境中的多主机文件同步

移动网络,广域网环境下,因终端频繁的加入与离开,以及网络的不稳定,造成节点的任意分隔.为避免网络分隔对可用性的影响,支持用户对任意副本的更新,文中实现了文件自动同步服务,Robin.通过设置在线服务器作为中转节点,可支持任意数目节点的扩展,在节点维护数据的弱一致性.Robin结合了状态比对和变化监控两种更新发现机制,增强同步的实时性.为解决并发更新对文件系统完整性的破坏,以及同步文件被占用造成合并更新失败等问题,Robin采用基于操作的冲突检测与处理.为不同的更新操作设置合并依赖条件,失败处理策略.为减少更新操作,Robin将文件系统日志中的多个变化事件合并为更新操作,保存在操作队列中,并进一步消除冗余操作.     

Conflicts in policy-based distributed systems management

Modern distributed systems contain a large number of objects and must be capable of evolving, without shutting down the complete system, to cater for changing requirements. There is a need for distributed, automated management agents whose behavior also has to dynamically change to reflect the evolution of the system being managed. Policies are a means of specifying and influencing management behavior within a distributed system, without coding the behavior into the manager agents. Our approach is aimed at specifying implementable policies, although policies may be initially specified at the organizational level and then refined to implementable actions. We are concerned with two types of policies. Authorization policies specify what activities a manager is permitted or forbidden to do to a set of target objects and are similar to security access-control policies. Obligation policies specify what activities a manager must or must not do to a set of target objects and essentially define the duties of a manager. Conflicts can arise in the set of policies. Conflicts may also arise during the refinement process between the high level goals and the implementable policies. The system may have to cater for conflicts such as exceptions to normal authorization policies. The paper reviews policy conflicts, focusing on the problems of conflict detection and resolution. We discuss the various precedence relationships that can be established between policies in order to allow inconsistent policies to coexist within the system and present a conflict analysis tool which forms part of a role based management framework. Software development and medical environments are used as example scenarios     

Version management for business process schema evolution

The current business environment changes rapidly, dictated by user requirements and market opportunities. Organisations are therefore driven to continuously adapt their business processes to new conditions. Thus, management of business process schema evolution, particularly process version control, is in great demand to capture the dynamics of business process schema changes. This paper aims to facilitate version control for business process schema evolution, with an emphasis on version compatibility, co-existence of multiple versions and dynamic version shifts. A multi-level versioning approach is established to specify dependency between business process schema evolutions, and a novel version preserving graph model is proposed to record business process schema evolutions. A set of business process schema updating operations is devised to support the entire set of process change patterns. By maintaining sufficient and necessary schema and version information, our approach provides comprehensive support for navigating process instance executions of different and changing versions, and deriving the process schema of a certain version. A prototype is also implemented for the proof-of-concept purpose.     

View integration: a step forward in solving structural conflicts

Thanks to the development of the federated systems approach on the one hand and the emphasis on user involvement in database design on the other, the interest in schema integration techniques is significantly increasing. Theories, methods and tools have been proposed. Conflict resolution is the key issue. Different perceptions by schema designers may lead to different representations. A way must be found to support these different representations within a single system. Most current integration methodologies rely on modification of initial schemas to solve the conflicts. This approach needs a strong interaction with the database administrator, who has authority to modify the initial schemas. This paper presents an approach to view integration specifically intended to support the coexistence of different representations of the same real-world objects. The main characteristics of this approach are the following: automatic resolution of structural conflicts, conflict resolution performed without modification of initial views, use of a formal declarative approach for user definition of inter-view correspondences, applicability to a variety of data models, and automatic generation of structural and operational mappings between the views and the integrated schema. Allowing users' views to be kept unchanged should result in improved user satisfaction. Each user is able to define his own view of the database, without having to conform to some other user's view. Moreover, such a feature is essential in database integration if existing programs are to be preserved     

基于逻辑和辩论的安全策略一致性研究

冲突检测和冲突消解是策略一致性研究的两个主要方向。现有的冲突检测算法时间复杂度高,且缺乏灵活性和扩展性。改变策略条件和基于优先级的冲突消解方法容易引起新的不一致性问题,而且优先权的赋予带有主观因素,难以实现。在此基础上,使用逻辑对策略和策略冲突进行形式化描述和分析,并提出了一种基于逻辑合一思想的多项式时间内的策略一致性检测算法;把策略冲突分为包容冲突、相交冲突和互补冲突,给出了一种包容冲突和相交冲突的自动解决方法,证明了该方法的可行性和完备性;利用辩论机制和理论对策略互补冲突进行了语义分析,为基于优先级的解决方案提供了理论基础;提出了一种策略互补冲突下的一致性策略子集的计算算法,并进行了复杂度分析。     

一种新的多版本增创算法

现有的对象复制技术是实时协同图形编辑系统中符合一致性模型的并发控制策略,但难以解决非几何属性以及三维绘图系统中的并发冲突情况.介绍了一个全新的一致性维护模型——基于版本复制的多版本技术,当并发操作发生冲突时,利用简化规则从目标版本派生出叶子物理版本,分别应用冲突操作到不同的叶子版本,有效地解决了非调和冲突操作的意愿保证.通过研究多版本技术的相关支持算法,在算法MOVIC的基础上,从各个冲突操作的最大共同相容操作着手,提出了基于相容冲突组的快速多版本增创算法FMVIC(Fast Multiple Versions Incremental Creation),减少了相容操作的比较次数,缩小了去冗余操作的范围.