面向实时传值系统的局部模型检测

为对实时传值系统进行模型检测，本文给出了时间符号迁移图作为系统的建模语言，以及实时谓词μ演算作为刻画性质的逻辑语言。本文给出了基于时间符号迁移图和实时谓词μ演算的一个模型检测算法，该算法动态生成和检测可达的状态空间，并且采用对数据变量on—the—fly实例化以及动态切分时间计值集合的方法，是一个局部算法。该算法不仅能处理基于有限域的变量，还可处理一类数据域无穷的变量(称“数据无关”变量)。     

基于符号迁移图的互模拟验证算法

符号迁移图是传值进程的一种直观而简洁的语义表示模型，该模型由Hennessy和Lin首先提出，随后又被Lin推广至带赋值的符号迁移图，本文不但定义了符号迁移图各种版本（基／符号）的强操作语义和强互模拟，提出了相互的强互模拟算法，而且通过引入符号观察图和符号同余图，给出了其弱互模拟等价和观察同余的验证算法，给出并证明了了τ－循环和τ－边消去定理，在应用任何弱互模拟观察同余验证算法之前，均可利用这些定理对所给符号迁移图进行化简。     

基于Linux的进程迁移机制设计

进程迁移在集群和分布式系统中发挥着重要的作用。进程迁移算法直接影响着迁移时间，目前流行的几种进程迁移算法的共同问题是迁移时间比较长，文中提出了一种改进的进程迁移算法，该算法借鉴了目前几种算法的优点。在此算法的基础上，设计了一种基于Linux-2．4．0内核的进程迁移机制。实验结果表明：这种迁移机制有效的提高了进程迁移的速度。     

带赋值符号迁移图的局部优化算法

带赋值符号迁移图（ＳＴＧＡ）是刻画一般传值进程的抽象计算模型,在ＳＴＧＡ上可以用“ｏｎ－ｔｈｅ－ｆｌｙ”实例化算法来验证传值进程之间的互模拟等价。由于ＳＴＧＡＡ的一个结点对应于具体迁移图的许多结点,在ＳＴＧＡ上所作的优化对提高互模拟判定算法的时间和空间效率会产生很大的影响。     

基于图知识迁移的蚁群算法参数选择

同时考虑蚁群算法的所有运行参数,提出一种基于图知识迁移的蚁群算法参数选择方法．首先,将包含知识（蚁群算法的运行参数）的源任务映射到一个高维的迁移空间,并通过迁移权值连接不同的源任务,构造一个模型迁移图;然后,扩展模型迁移图使其包含目标任务,并利用图论的知识学习迁移函数;最后,通过最小二乘法自主地给目标任务分配一个优化的运行参数组合．机器人路径规划问题的仿真结果验证了该方法的智能性、快速性与合理性．     

GPLP:基于标签传播的大图多级划分算法

图数据划分问题是大图处理系统的关键问题,制约着图处理系统的计算效率。目前可用的划分算法可分为随机划分和多层次划分,已有的算法难以在划分速度和划分效果两个方面同时满足要求。提出了一种新的基于标签传播的多级划分算法GPLP,该方法将图划分过程分为数据标记、图粗糙化和数据迁移三部分,在多级划分框架下采用标签传播算法,并对其进行了改进。从数据划分时间和迭代计算时间两个方面对比GPLP算法、Hash算法和Par METIS算法的性能,实验结果表明GPLP算法能够提高迭代计算速度,减少了划分时间,并且数据规模越大,其优势越明显。     

贪心线性推移负载平衡算法

针对环与线性阵列的负载平衡速度较慢与迁移量较大的问题,提出一种贪心线性推移平衡算法。该算法适用于任何具有哈密尔顿通路的图结构网络。其平衡过程的负载迁移量一般不大,平衡负载速度较快。对二维网状网等网络结构的贪心线性推移平衡算法进行改进,得到分二阶段的贪心线性推移平衡算法。实验结果表明,此类改进在平衡条件减弱时能较大地提高算法的时间性能。     

面向目标的迁移工作流迁移路径的寻址与优化*

给出了一种面向目标的迁移工作流迁移路径的寻址与优化算法,研究了工作流的执行主体——迁移实例在动态环境中完成给定目标的迁移路径问题。借助ANDOR图理论,给出了算法的基本框架。     

针对移动云计算任务迁移的快速高效调度算法

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。     

上下文感知的分布式缓存数据重均衡方法

为了改善数据重均衡的效果及减小数据迁移对系统性能的影响,提出一种上下文感知的数据重均衡方法.构建迁移时间预测模型,以刻画虚拟机环境上下文对数据迁移的影响,据此提出基于细粒度资源监测的上下文感知的数据重均衡算法CADR.实验结果表明,该迁移时间预测模型具有较低的错误率;CADR算法与传统数据重均衡算法相比,能够提供更好的均衡效果及更短的迁移时间.     

Axiomatising timed automata

Timed automata has been developed as a basic semantic model for real time systems. Its algorithmic aspects for automated analysis have been well studied. But so far there is still no satisfactory algebraic theory to allow the derivation of semantical equivalence of automata by purely syntactical manipulation. The aim of this paper is to provide such a theory. We present an inference system of timed bisimulation equivalence for timed automata based on a CCS-style regular language for describing timed automata. It consists of the standard monoid laws for bisimulation and a set of inference rules. The judgments of the proof system are conditional equations of the form where is a clock constraint and t,u are terms denoting timed automata. The inference system is shown to be sound and complete for timed bisimulation. The proof of the completeness result relies on the notion of symbolic timed bisimulation, adapted from the work on value–passing processes. Received: 10 May 2001 / 22 October 2001     

Statistical model checking of Timed Rebeca models

The actor-based language, Timed Rebeca, was introduced to model distributed and asynchronous systems with timing constraints and message passing communication. A toolset was developed for automated translation of Timed Rebeca models to Erlang. The translated code can be executed using a timed extension of McErlang for model checking and simulation. In this work, we added a new toolset that provides statistical model checking of Timed Rebeca models. Using statistical model checking, we are now able to verify larger models against safety properties compared to McErlang model checking. We examine the typical case studies of elevators and ticket service to show the efficiency of statistical model checking and applicability of our toolset.     

Timed high-level nets

Petri nets have been widely used for modeling and analyzing concurrent systems. Several reasons contribute to their success: the simplicity of the model, the immediate graphical representation, the easy modeling of asynchronous aspects, the possibility of reasoning about important properties such as reachability, liveness, boundedness. However, the original model fails in representing two important features: complex functional aspects, such as conditions which rule the flow of control, and time. Due to that, two different classes of extensions of Petri nets have been proposed: high-level nets and timed Petri nets. High-level nets allow the representation of functional aspects in full details, but do not provide a means for representing time; on the other hand, timed Petri nets have been thought for time representation, but they do not provide a means for representing detailed functinal aspects. Thus, these two important aspects cannot be mastered together. In particular, it is difficult to express relationships between time and functional aspects.This paper investigates the relationships between high-level nets and timed Petri nets, thus extending a first set of results published in a previous paper, where a unifying Petri net based model for time representation has been proposed. It first recalls how time can be represented in a Petri net extension called ER nets, and assesses its generality. It then investigates the relationships of ER nets with the best known high-level nets. In particular it shows the overall equivalence of ER nets, Colored Petri nets and Predicate/Transition nets, and extends the mechanism for time representation introduced in ER nets to both Colored Petri nets and Predicate/Transition nets. It also shows that these models cannot be simplified without significantly constraining the timing aspects that can be modeled.     

时间符号迁移图上的可达性分析

提出了以时间符号迁科为建模语言、基于可达性分析的模型检测算法，并给出了算法的正确性证明。该算法可被用于硬件设计和通信协议验证等领域。     

Weak bisimulation for Probabilistic Timed Automata

We are interested in describing timed systems that exhibit probabilistic behaviour. To this purpose, we consider a model of Probabilistic Timed Automata and introduce a concept of weak bisimulation for these automata, together with an algorithm to decide it. The weak bisimulation relation is shown to be preserved when either time, or probability is abstracted away. As an application, we use weak bisimulation for Probabilistic Timed Automata to model and analyze a timing attack on the dining cryptographers protocol.     

Timed CSP = Closed Timed Automata

We study the expressive power of an augmented version of Timed CSP and show that it is precisely equal to that of closed timed automatatimed automata with closed invariant and enabling clock constraints. We also show that this new version of Timed CSP is expressive enough to capture the most widely used specifications on timed systems as refinements between processes, and moreover that refinement checking is amenable to digitisation analysis. As a result, we are able to verify some of the most important timed specifications, including branching-time liveness properties such as timestop-freedom and constant availability, using the model checker FDR (a commercial product of Formal Systems (Europe) Ltd.).     

Temporal Proof Methodologies for Timed Transition-Systems

We extend the specification language of temporal logic, the corresponding verification framework, and the underlying computational model to deal with real-;time properties of reactive systems. The abstract notion of timed transition systems generalizes traditional transition systems conservatively: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound timing constraints on transitions. This framework can model real-time systems that communicate either through shared variables or by message passing and real-time issues such as timeouts, process priorities (interrupts), and process scheduling. We exhibit two styles for the specification of real-time systems. While the first approach uses time-bounded versions of the temporal operators, the second approach allows explicit references to time through a special clock variable. Corresponding to the two styles of specification, we present and compare two different proof methodologies for the verification of timing requirements that are expressed in these styles. For the bounded-operator style, we provide a set of proof rules for establishing bounded-invariance and bounded-responce properties of timed transition systems. This approach generalizes the standard temporal proof rules for verifying invariance and response properties conservatively. For the explicit-clock style, we exploit the observation that every time-bounded property is a safety property and use the standard temporal proof rules for establishing safety properties.     

有限精度时间自动机的可达性检测

为了缓解状态空间爆炸问题,减小模型检测过程中生成的状态空间,加快模型检测速度,引入有限精度时间自动机(finite precision timed automata,简称FPTA)作为实时系统的形式模型,并提出了一种数据结构SDS(series of delay sequence)符号化表示状态空间中的状态集.FPTA只记录时钟变量的整数值及时钟变化的先后次序,从而减小生成的状态空间.在一定的时间约束下,Alur与Dill提出的时间自动机的可达性检测可简化为FPTA的可达性检测.举例描述了状态空间的生成过程和表示方法.最后,列出部分初步的实验结果,分析了SDS的特点及不足.     

Timed Semantics of Message Sequence Charts Based on Timed Automata

Message Sequence Charts (MSCs) provide a way for quick and easily understandable modelling of concurrent systems. Apart from their intuitive semantics easily deduced from their visual syntax, there is a formally defined semantics—Unfortunately, the semantics intuitively assigned to them is sometimes at odds with the formal semantics. In this paper, we will show an alternative approach to the semantics of MSCs, which will enable us to formally model their timed behaviour. Furthermore, we show how some generalizations of ordering events can lead to a language better suited to model real-world requirements. To ease the task of analyzing (High-Level) MSCs, we identify a subclass of those which can be translated into finite (timed of untimed) automata and specify the translation, thus laying the foundation for model checking.