Efficient Detection of Channel Predicates in Distributed Systems

This paper discusses efficient detection of global predicates in a distributed program. Previous work in this area required predicates to be specified as a conjunction of predicates defined on individual processes. Many properties in distributed systems, however, use the state of channels, such as “the channel is empty,” or “there is a token in the channel.” In this paper, we introduce the concept of alinearchannel predicate and provide efficient centralized and distributed algorithms to detect any conjunction of local and linear channel predicates. The class of linear predicates is fairly broad. For example, classic problems such as detection of termination and computation of global virtual time are instances of conjunctions of linear channel predicates. Linear predicates can be functions of the number of messages in the channel, or can be based upon the actual contents of the messages. The main application of our results are in debugging and testing of distributed programs. For these applications it is important to detect thefirststate where some predicate is true. We show that this first state is uniquely defined if and only if linear predicates are used.     

观察分布式计算——全局性质检测的方法学研究

程序观察研究程序一次执行的行为特性，由于缺乏全局信息，观察分而式程序是当相困难的，分布式程序观察的核心是全局性质检测问题，文中提出了分布式程序观察－全局性质检测的方法学分类，讨论了全局性质检测的通用方法，检测稳定性质的快照方法，检测不稳定性持贩格方法，将动态性质检测转换为语言识别问题，同时讨论了检测特殊结构全局性质的方法，强稳定性质和局部稳定性质，合取不稳定性质及流／波模式的动态性质。     

软件容错：技术与展望

本文主要给出现有主流软件容错技术的一个综述。首先从传统软件容错技术开始，介绍设计多样性和数据多样性；然后介绍主流的软件容错新技术，如重配置与重恢复、指令复制错误探测、SWIFT等，同时，站在软件容错用于处理嵌入式系统硬件暂态故障的角度对这些技术进行了分析；最后在对它们比较的基础上探讨软件容错技术的可能发展方
向。     

结合语句执行补集的程序错误定位

基于频谱的错误定位方法一般利用覆盖信息为每条语句度量出错的可能,即可疑度,通过逐条检查按可疑度值降序排列的语句序列来确定错误语句.针对已有的方法大多只考虑覆盖信息中语句执行信息的问题,分析了语句执行补集对错误定位的积极影响,进一步提出了在语句执行信息基础上结合语句执行补集的错误定位方法.实验结果表明,与其他方法相比,所...     

基于偶然性正确测试用例发现的错误定位方法

软件错误定位是目前软件工程领域的重要研究课题,其中基于程序谱的错误定位（CFL）是一类重要的方法。偶然性正确测试用例对于CFL有着很大的负面影响,因此如何发现该类测试用例或者避免它们对CFL的影响对于提高CFL方法的定位效果有着重要的意义。通过分析偶然性正确对CFL定位方法的影响,发现一种没有误判率（false positive）的寻找偶然性正确测试用例的方法。在此基础上,提出了一种基于偶然性正确测试用例发现的CFL定位方法。通过实验表明,该方法可以普遍改善已有CFL方法的定位效果。     

开放环境特性感知技术

提出了一个开放环境特性描述框架.该框架支持便捷地、形式化地描述异步环境的各种特性,包括那些既有技术不能处理的时序特性.该框架还引入了谓词检测技术,支持高效的环境特性感知机制的实现.开发了一个开放环境特性感知中间件平台,并通过详细的案例分析展示了如何基于所提出的环境特性描述框架与中间件平台,高效地感知环境特性,支持可信软件系统的构建.     

A chained-matrices approach for parallel computation of continued fractions and its applications

A chained-matrices approach for parallel computing thenth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction inO(logn) time on the EREW PRAM model or a network withO(n/logn) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as ande, inO(logm) time by usingO(m/logm) processors for a result withm-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the generalmth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.This work was supported in part by National Science Council of the Republic of China under Contract NSC 77-0408-E002-09.     

Distributed oblivious function evaluation and its applications

This paper is about distributed oblivious function evaluation (DOFE). In this setting one party (Alice) has a function f(x), and the other party (Bob) with an input α wants to learn f(α) in an oblivious way with the help of a set of servers. What Alice should do is to share her secret function f(x) among the servers.Bob obtains what he should get by interacting with the servers. This paper proposes the model and security requirements for DOFE and analyzes three distributed oblivious polynomial evaluation protocols presented in the paper.     

软件第三方测评

软件测评是许多软件交付用户前的最后一个环节,对提高软件的质量起着重要作用.所谓的软件第三方测评,是由具有相关资质的独立第三方测评机构根据委托方的要求,依据相关标准,对被测软件的质量进行全面的测试和评价.结合自身工作经验介绍了软件第三方测评的目的,详细论述了软件第三方测评的过程及其工作产品,最后对如何更好地开展软件第三方测评提出了一些建议.     

人计算研究现状及发展趋势

针对计算机无法或难以解决的问题,而提出的结合人的能力与分布式思想的人计算理念,在信息智能化的背景下得到了充分的关注。详细描述了人计算的内涵、特性、并与相近概念的区分,并对迄今为止的人计算研究方式以及人计算的设计准则进行了分类与整理。最后,总结归纳人计算现有的研究方向,并指出未来可能的研究与发展趋势。     

面向分布式图计算作业的容错技术研究综述

随着图数据规模的日益庞大和图计算作业的日益复杂,图计算的分布化成为必然趋势.然而图计算作业在运行过程中面临着分布式图计算系统内外各种来源的非确定性所带来的严峻的可靠性问题.首先分析了分布式图计算框架中不确定性因素和不同类型图计算作业的鲁棒性,并提出了基于成本、效率和质量3个维度的面向分布式图计算作业的容错技术评估框架,...     

Performance comparison of checkpoint and recovery protocols

Checkpoint and rollback recovery is a well‐known technique for providing fault tolerance to long‐running distributed applications. Performance of a checkpoint and recovery protocol depends on the characteristics of the application and the system on which it runs. However, given an application and system environment, there is no easy way to identify which checkpoint and recovery protocol will be most suitable for it. Conventional approaches require implementing the application with all the protocols under consideration, running them on the desired system, and comparing their performances. This process can be very tedious and time consuming. This paper first presents the design and implementation of a simulation environment, distributed process simulation or dPSIM, which enables easy implementation and evaluation of checkpoint and recovery protocols. The tool enables the protocols to be simulated under a wide variety of application, system, and network characteristics. The paper then presents performance evaluation of five checkpoint and recovery protocols. These protocols are implemented and executed in dPSIM under different simulated application, system, and network characteristics. Copyright © 2003 John Wiley & Sons, Ltd.     

计算机系统开发中的可信性评价概述

本文将高可信计算机系统的开发过程划分为需求，设计，实现和集成四个阶段，分别介绍各阶段中与可信性有关的任务及可信性评价技术的应用。     

基于UML图和动态切片的回归测试研究

重点将UML图和动态切片应用于回归测试中。针对现在应用于软件开发的UML图不能很好地满足软件测试的要求,引入了时序状态图和改进后的状态图,对两种图进行形式化定义,并且通过实例说明定义内容,其中时序状态图用于类间测试,改进后的状态图用于类内测试。对定义的图进行切片分析,形成测试步骤和测试算法。网上购物实例表明时序状态图和改进状态图可以提高回归测试效率。     

Performance and effectiveness trade‐off for checkpointing in fault‐tolerant distributed systems

Checkpointing has a crucial impact on systems' performance and fault‐tolerance effectiveness: excessive checkpointing results in performance degradation, while deficient checkpointing incurs expensive recovery. In distributed systems with independent checkpoint activities there is no easy way to determine checkpoint frequencies optimizing response‐time and fault‐tolerance costs at the same time. The purpose of this paper is to investigate the potentialities of a statistical decision‐making procedure. We adopt a simulation‐based approach for obtaining performance metrics that are afterwards used for determining a trade‐off between checkpoint interval reductions and efficiency in performance. Statistical methodology including experimental design, regression analysis and optimization provides us with the framework for comparing configurations, which use possibly different fault‐tolerance mechanisms (replication‐based or message‐logging‐based). Systematic research also allows us to take into account additional design factors, such as load balancing. The method is described in terms of a standardized object replication model (OMG FT‐CORBA), but it could also be applied in other (e.g. process‐based) computational models. Copyright © 2006 John Wiley & Sons, Ltd.     

Efficient detection of a locally stable predicate in a distributed system

We present an efficient approach to detect a locally stable predicate in a distributed computation. Examples of properties that can be formulated as locally stable predicates include termination and deadlock of a subset of processes. Our algorithm does not require application messages to be modified to carry control information (e.g., vector timestamps), nor does it inhibit events (or actions) of the underlying computation. The worst-case message complexity of our algorithm is O(n(m+1))$O(n(m+1))$, where n$n$ is the number of processes in the system and m$m$ is the number of events executed by the underlying computation. We show that, in practice, its message complexity should be much lower than its worst-case message complexity. The detection latency of our algorithm is O(d)$O(d)$ time units, where d$d$ is the diameter of communication topology. Our approach also unifies several known algorithms for detecting termination and deadlock. We also show that our algorithm for detecting a locally stable predicate can be used to efficiently detect a stable predicate that is a monotonic function of other locally stable predicates.     

装备自动测试系统软件的可测试性设计与分析

针对导弹通用自动测试系统的功能与实现,对系统的软件部分进行可测试性设计分析研究。结合目前测试系统软件的测试与排错技术研究,提出了几种提高软件可测试性的可行性设计技术。实践证明,这些技术可以显著提高自动测试系统软件的可测试性。     

Applying a dynamic testability technique to debugging certain classes of software faults

Testability, the tendency for software to reveal its faults during testing, is an important issue for verification and quality assurance. But testability can also be used to good advantage as a debugging technique. Although this concept is more general, we will illustrate it with a specific example: propagation analysis.Propagation Analysis (PA) is a technique for predicting the probability that a data state error affects program output. PA is a technique that produces information about a piece of software's testability. PA bases its prediction on empirical measurement of the probability that an artificial data state error affects program output. After obtaining propagation analysis information for a program and obtaining a failure probability estimate for the program during execution we build a model that can be used to identify possible sites of missing-assignment faults of the form x f(x). Thus we can apply the testability technique PA as a debugging tool.This work supported by a National Research Council NASA-Langley Resident Research Associateship and NASA-Langley Grant NAG-1-884.     

轻量级大数据运算系统Helius

针对Spark数据集不可变,以及Java虚拟机（JVM）依赖环境引起的代码执行、内存管理、数据序列化/反序列化等开销过多的不足,采用C/C++语言,设计并实现了一种轻量级的大数据运算系统--Helius。Helius支持Spark的基本操作,同时允许数据集整体修改;同时,Helius利用C/C++优化内存管理和网络传输,并采用stateless worker机制简化分布式计算平台的容错恢复过程。实验结果显示：5次迭代中,Helius运行PageRank算法的时间仅为Spark的25.12%~53.14%,运行TPCH Q6的时间仅为Spark的57.37%;在PageRank迭代1次的基础上,运行在Helius系统下时,master节点IP接收和发送数据量约为运行于Spark系统的40%和15%,而且200 s的运行过程中,Helius占用的总内存约为Spark的25%。实验结果与分析表明,与Spark相比,Helius具有节约内存、不需要序列化和反序列化、减少网络交互以及容错简单等优点。     

一种容错的分布式服务器复制与更新协议

针对分布式环境提出一种容错的文件数据复制与更新机制,其算法/协议建立在分布式算法理论的基础上,具有较强的容错性、故障恢复透明性和较高的效率,支持服务器同步和异步两种复制模式以及客户机启动与服务器启动两种工作方式。该机制可广泛应用于Internet分布式文件系统、分布式数据库、WEB镜像服务器以及分布式软件分发、群集服务器等应用中。