Optimizing vote and quorum assignments for reading and writingreplicated data

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered     

基于Quorum系统容错技术综述

Quorum系统是一种新型冗余拓扑的集合系统。在“冗余”设计的基础上，quorum通过交叉的结点把有效数据复制到其他quorum的结点中，增加了Quorum系统数据冗余性。当某些结点发生故障或者错误时，通过选举协议，从含有故障结点quorum的有效结点中选举出有效数据；或者采用互斥协议，从不含故障或者错误结点的有效quorum的结点中获得有效数据，系统仍能可靠运行。分析了各种Quorum肌系统的容错方式、性能比较，探讨了Quorum系统发展中需要改进的关键问题，并展望了未来的研究方向。     

Binary vote assignment on a grid for efficient access of replicated data

Data replication can be used to improve the availability of data in a distributed database system. In such a system, a mechanism is required to maintain the consistency of the replicated data. Grid structure (GS) technique based on quorum is one of the latest solutions for performing this while providing a high availability of the system. It was shown in the previous study, that it still requires a bigger number of copies be made available to construct a quorum. So it is not suitable for the large systems. In this paper, we propose a technique called the binary vote assignment on grid (BVAG) technique by considering only neighbors have the replicated data. In comparison to the GS technique, BVAG requires lower communication cost for an operation, while providing higher data availability, which is preferred for large systems.     

Compositionality and correctness of fault tolerant patterns in HOL4

In the development of critical systems, it is common practice to make use of redundancy in order to achieve higher levels of reliability. There are well established design patterns that introduce redundancy and that are widely documented and adopted by the industry. However there have been few attempts to formally verify them. In this work, we modelled in the HOL4 system such design patterns, which we call here fault tolerant patterns. We illustrate our approach by modelling three classical fault tolerant patterns: Homogeneous Redundancy, Heterogeneous Redundancy and Triple Modular Redundancy. Our model takes into account that the original system (without redundancy) computes a certain function with some delay and is amenable to random failures.We proved that our fault tolerant patterns preserve the behaviour of its replicated subsystems. The notion of correctness adopted makes use of interval arithmetic and is restricted to functional behaviour. Timing is not regarded as part of the functional behaviour in this work. Therefore, real-time systems are not the focus of our approach. We also proved that our fault tolerant patterns are compositional in the sense that we can apply fault tolerant patterns consecutively and for an arbitrary number of times. The consecutive application of our patterns still results in a system that computes a certain function with some delay and amenable to random failures. We developed a case study that verifies that a fault tolerant pattern applied to a simplified avionic Elevator Control System preserves its original behaviour. This work was done in collaboration with the Brazilian aircraft manufacturer Embraer.     

航空发动机被动容错控制系统鲁棒性设计

针对航空发动机发生故障时系统的容错能力问题,设计了基于特征结构配置方法的容错控制系统。首先分析了被动容错控制的特点和优点,然后采用特征结构配置的方法,在配置系统极点的同时,还配置系统的特征向量,并对系统进行重新调节以获得整个系统在故障发生后的稳定性与可靠性,给出了特征结构配置方法的具体设计步骤。最后,针对某型航空发动机的设计工况点模拟系统发生故障,即参数发生摄动时,对所设计的容错系统鲁棒性进行了分析计算。仿真算例结果表明,所设计的容错系统具有较好的抗干扰能力,即较好的鲁棒性。     

Performance characterization of quorum-consensus algorithms forreplicated data

The authors develop a model and define performance measures for a replicated data system that makes use of a quorum-consensus algorithm to maintain consistency. They consider two measures: the proportion of successfully completed transactions in systems where a transaction aborts if data is not available, and the mean response time in systems where a transaction waits until data becomes available. Based on the model, the authors show that for some quorum assignment there is an optimal degree of replication beyond which performance degrades. There exist other quorum assignments which have no optimal degree of replication. The authors also derive optimal read and write quorums which maximize the proportion of successful transactions     

分布、实时、容错一体化设计方法研究

针对分布式航天器系统的运行环境和特点，对嵌入式系统在空间环境、实时、容错、分布上的需求进行了分析，提出了分布、实时、容错一体化的嵌入式系统设计方法，从满足实时要求下的实时容错能力、免疫与自愈相结合的综合容错能力、单节点的容错与节点间容错相结合的分布容错能力和多种容错方法集成等4个方面，对设计方法进行了阐述。     

冗余机械臂运动学优化设计

该文主要从机械臂运动学的角度,定义了故障容错机械臂,巧妙地论证了冗余故障容错机械臂应该具备的自由度数,以及针对不同的任务要求,设计故障容错机械臂的方法。通过将任务空间抽象简化为一系列的特征点,建立机械臂参数与理想值相关的罚函数,选择有效的优化算法,设计出了通用一阶故障容错平面位置机械臂,通用一阶故障容错空间位置机械臂,以及特定任务一阶故障容错平面位置机械臂。建立起完整的故障容错机械臂的设计方法。     

Branch-and-bound task allocation with task clustering-based pruning

We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state–space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state–space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state–space searching approach feasible for practical use.     

Applying combinatorial optimization metaheuristics to the golf scramble problem

One typical golf tournament format is termed a 'Scramble,' comprised of four-person teams. The participants are rank-ordered into four equally sized 'flights' based on integer-valued handicaps determined by skill level. One participant from each flight is selected to make up a team. Of interest is the assignment of teams in an 'equitable' fashion, where equitable is defined as minimizing the difference between the largest and smallest sum of the handicaps. For a typical tournament of 36 teams there are over 10 ¹²⁴ unique assignments. Since in general there are duplicate handicap values, the number of 'equivalent' assignments is reduced (but still very large). Various heuristics are explored for efficiently identifying an optimal or near optimal solution. These include descent heuristics, simulated annealing, tabu search, and genetic algorithms. Genetic algorithms outperform other heuristics by taking advantage of the problem structure.     

Deterministic approximation of marginal probabilities in Bayes nets

Computation of marginal probabilities in Bayes nets is central to numerous reasoning and automatic decision-making systems. This paper presents a deterministic approximation scheme for this hard problem that supplies provably correct bounds by aggregating probability mass in independence-based (IB) assignments. It refines belief updating methods. It approximates posterior probabilities by finding a small number of the highest probability complete (or evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer assignments are sufficient, and a good approximation can be obtained efficiently. Two classes of algorithms for finding high-probability assignments are suggested: best-first heuristic search and a special integer linear program (ILP). Since IB assignments may be overlapping events in probability space, accumulating the mass in a set of assignments may be hard. In the ILP variant, it is easy to avoid the problem by adding equations that prohibit overlap. In the best-first search algorithm, other schemes are necessary, but experimental results suggest that using inclusion-exclusion (potentially exponential-time in the worst case) in the overlap cases is not too expensive for most problem instances     

容错计算机系统可靠性评估中的覆盖率问题

覆盖率是容错系统设计和评估中的重要概念。该文介绍了采用行为分解技术建立和求解覆盖率模型的方法,总结了用故障注入技术估计覆盖率需要考虑的几个问题。以一个双机容错系统的评估为例,说明了这些方法在容错系统可靠性评估中的应用。     

突发性故障模式下实时任务的优先级分配策略

在容错实时系统中,可调度性分析是确保实时任务在限定时间内完成的重要手段。分析了突发性故障模式的可调度性问题,针对该故障模式下已有策略的不足,设计了优先级分配策略,并根据策略的性质实现了容错优先级变迁因子的搜索算法。深入的分析和实验证明,这种策略能够有效地提高系统的容错能力。     

Multiobjective optimization–based fault‐tolerant flight control system design

The loss of measurements used for controller scheduling or envelope protection in modern flight control systems due to sensor failures leads to a challenging fault‐tolerant control law design problem. In this article, an approach to design such a robust fault‐tolerant control system, including full envelope protections using multiobjective optimization techniques, is proposed. The generic controller design and controller verification problems are derived and solved using novel multiobjective hybrid genetic optimization algorithms. These algorithms combine the multiobjective genetic search strategy with local, single‐objective optimization to improve convergence speed. The proposed strategies are applied to the design of a fault‐tolerant flight control system for a modern civil aircraft. The results of an industrial controller verification and validation campaign using an industrial benchmark simulator are reported.     

用软件实现的故障注入工具评估错误检测机制

故障注入是容错计算机系统可靠性评估的征要手段,本文介绍了软件实现的故障注入工具ＳＯＢＦＩ设计与实现,用ＳＯＢＦＩ对ＲＳ６０００工作站的错误检测机制和两种软件实现的错误检测机制进行了试验评估,结果表明,在非容错商用计算机系统中加入简单折软件实现的错误检测机制,也呆以达到很高的错误检测覆盖率。     

基于反射的容错CORBA系统的设计与实现

容错是实现系统可靠性的一个重要手段。单一的容错策略已经不能满足当今分布式系统动态变化的要求,因此容错策略可配置的重要性就凸现出来。该文结合编译期反射和运行期反射,提出了可配置CORBA容错结构,并使用OpenC＋＋和拦截器实现了一个容错CORBA原型系统。该方法不需要修改CORBA ORB,而只需要对应用作极少的改动。     

副版本不可抢占的全局容错调度算法

容错是硬实时系统的关键能力,容错调度算法可以在有错误发生的情况下满足任务的实时性需求.在主副版本机制的容错调度算法中,主版本出错后留给副版本运行的时间窗口小,副版本容易错失截止期.针对副版本需要快速响应的问题,提出副版本不可抢占的全局容错调度算法FTGS-NPB（fault-tolerant global scheduling with non-preemptive backups）,赋予副版本全局最高优先级,使副版本在主版本出错后可以立刻获得处理器资源,并且在运行过程中不会被其他任务抢占.这样,副版本可以在最短时间内响应.分别基于截止期分析和响应时间分析建立了FTGS-NPB的可调度性测试,并分析了两种可调度性测试分别适用于不同的优先级分配算法.仿真实验结果表明,FTGS-NPB可以有效地减少实现容错的代价.     

Exact,almost and delayed fault detection: an observer based approach

This paper considers the problem of fault detection and isolation in continuous- and discrete-time systems while using zero or almost zero threshold. A number of different fault detection and isolation problems using exact or almost exact disturbance decoupling are formulated. Solvability conditions are given for the formulated design problems together with methods for appropriate design of observer based fault detectors. The 𝓁-step delayed fault detection problem is also considered for discrete-time systems. Moreover, certain indirect fault detection methods such as unknown input observers, eigenstructure assignment, factorization, and parity equation approaches are generalized by including the almost estimation methods in addition to exact estimation methods. Copyright © 1999 John Wiley & Sons, Ltd.     

ZFS文件系统中双容错编码性能的研究

ZFS是Sun推出的一款革新性的文件系统,它支持用户构建镜像以及单容错/双容错的软Raid。其双容错编码方案采用的是Reed-Solomon编码(RS码)。由于RS码是基于有限域运算,编码/解码时间复杂性差是其根本性的缺陷。ZFS对写操作的处理采用的是聚合后追加的方式而非传统的覆盖方式,每次写操作都会进行一次编码计算。因此,编码计算性能是影响文件系统整体性能的重要因素之一。本文的工作是将RDP这一基于奇偶校验的双容错编码与ZFS相结合,替代Reed-Solomon编码,以优化文件系统写操作的性能。我们设计了Cache优化的RDP编码算法,在ZFS中进行了实现,并通过实验验证了这一方法的有效性。