Aperiodic Checkpoint Placement Algorithms—Survey and Comparison

In this article we summarize some aperiodic checkpoint placement algorithms for a software system over infinite and finite operation time horizons, and compare them in terms of computational accuracy. The underlying problem is formulated as the maximization of steady-state system availability and is to determine the optimal aperiodic checkpoint sequence. We present two exact computation algorithms in both forward and backward manners and two approximate ones;constant hazard approximation and fluid approximation, toward this end. In numerical examples with Weibull system failure time distribution, it is shown that the combined algorithm with the fluid approximation can calculate effectively the exact solutions on the optimal aperiodic checkpoint sequence.

众包质量控制策略及评估算法研究

随着Internet技术的快速发展,众包作为一种灵活有效的解决问题方式,开始受到人们越来越多的关注.由于众包的自由松散组织模式,使得如何有效地控制任务完成质量,并将欺骗类型工作者识别出来,成为目前众包研究中一个急需解决的问题.文中基于对众包工作者提交结果的评估与分析,提出了一种阶段式的动态质量控制策略,同时给出了一个组合式众包结果质量评估方法框架.经过实际数据的测试,文中提出的质量控制策略和众包结果质量评估方法具有较好的效果.

分布式系统中的检查点算法

检查点能够保存和恢复程序的运行状态．它在进程迁移、容错、卷回调试等领域都有重要的应用．本文对分布式系统中的检查点算法进行了详细的分类评述．检查点算法可分为单进程和分布式程序检查点算法，分布式程序检查点算法又可分为异步检查点算法和一致检查点算法．同时本文系统介绍了改进检查点算法性能的典型方法．这些改进算法主要采用两个策略来减少算法的开销与延迟：一是减少检查点文件中需要存储的信息量，如增量算法等；二是提高检查点操作与目标程序运行的并行性，如主存算法等．最后，文章讨论了目前检查点算法的局限性和进一步的工作．

基于检查点算法的网格计算容错机制研究

文章设计了一个基于网格计算的任务迁移与恢复模型,指出了该模型的各模块功能架构,并进一步分析和比较了该模型容错的检查点存储方式及其信息编码算法,最后通过实现一个基于Checksum算法的容错CG求解器实例表明相关理论的有效性。

毛竹力学强度标准值和设计值的确定方法

选取3~6年生毛竹作为研究对象,收集了569个数据,分别对毛竹强度标准值和设计值的确定提出方法。采取次序统计法获得毛竹的顺纹抗拉、顺纹抗压、抗弯和顺纹抗剪强度标准值,分别为145.33、45.58、104.33和9.52MPa。用设计验算点逆算法建立适合竹材的功能函数,在满足可靠度的要求下,得到毛竹对应的强度设计值为38.19、22.32、37.19和4.73 MPa。通过将毛竹的强度设计值与重组竹、格鲁斑胶合竹对比,得出设计验算点逆算法计算毛竹设计值可行。

嵌入式内存数据库的恢复及重装算法研究

在嵌入式内存数据库系统中,系统崩溃时数据库主拷贝存于易失性内存中,因此需要把数据库主拷贝从外存重装到内存。本文在嵌入式内存数据库恢复技术的基础上讨论了几种重装算法,提出了嵌入内存数据库的数据优先级重装算法,并进行了实验验证。结果表明,数据优先级重装算法比顺序重装算法性能高。

基于动态分组的两级检查点算法

为了降低设置检查点的时间和空间开销,提出了一种两级检查点算法,其中组级采用协调检查点算法,系统级采用单阶段检查点算法.该算法基于分布式动态分组策略,通过发送分组来确保分组间不会产生孤儿消息,实现了由传统的两阶段提交算法到单阶段算法的转变.实验结果表明,算法执行时间较低,时间复杂度由通常的O(n2)降低到O(n),具有较强的实用性.

基于索引的准同步检查点的重新计时策略

基于索引的分布式检查点算法利用了Lamport逻辑时钟的思想来保证形成全局一致性检查点(或者恢复线)。作为一种准同步方法,基于索引的检查点算法具有异步检查点算法的灵活性,且能像同步算法一样避免多米诺效应。本文在著名的BCS算法的基础上提出了一种减少基本检查点数目的优化策略———重新计时法。最后,通过模拟实验证明了这种改进策略的有效性。

可逆排序算法的分析与实现

使软件系统基于当前状态恢复先前某一状态的方法通常有两种:检查点和反向计算。为比较这两种方法的实现代价,以如何实现最低代价的可逆排序为例,将增量检查点技术应用于简单选择排序算法,实现了一种通过增量保存程序运行时系统状态的变化信息以恢复系统先前某一状态的排序算法,并通过反向计算技术实现了一种无需系统状态历史信息仅通过系统当前状态和程序自身逻辑便恢复先前状态的可逆排序算法。通过大量测试用例验证了上述两类算法的正确性,并得出在大规模且数据交换频繁的场景下反向计算排序算法远优于检查点排序算法的结论。

基于拜占庭容错的前摄恢复算法

针对现有拜占庭容错中的恢复算法不适用于主动复制品的这一问题,提出支持有状态复制品的前摄恢复算法。每个复制品维护一个恢复队列。当到达一个检查点后,使用该前摄恢复算法复制品检查恢复队列,在服务复制品发生错误前,提前将复制品恢复成正确的状态。如果复制品已经出错,该算法也适用。实验分析结果显示算法的有效性。

分布式系统检查点算法中程序卷回时文件系统的状态恢复

检查点技术,也称为“回溯恢复”,是软件容错的重要手段,它主要用于保存和恢复程序的运行状态。在分布式计算和并行计算系统中有十分重要的作用。该文从减少检查点的开销角度,对分布式系统检查点算法中关于程序卷回时文件系统状态的恢复问题进行了分析讨论和进一步的研究。

几种改进分布式共享存储器系统性能的算法

分布式共享存储器 (DSM)系统结合了共享存储器并行计算机编程容易和消息传递多计算机的可扩展性。在此介绍了 DSM系统中的检查点与卷回恢复算法、共享粒度的动态适应算法 ,以及各种算法的原理和算法对 DSM系统性能的影响。

具有O（n）消息复杂度的非阻塞检查点算法①

为了用检查点设置及回卷恢复技术提高并行分布式系统容错性能时降低设置检查点的时间和空间开销，提出了一种非阻塞协调检查点算法。与传统的两阶段提交算法不同，该算法是单阶段提交算法，可跳过临时检查点阶段直接获得永久检查点，减少了同步控制消息的数量，加快了检查点的形成时间。它通过发送进程排除孤儿消息，实现了并行计算；通过设置检查点算法启动周期，解决中途消息问题。该算法的时间复杂度由通常的O（n^2）降低到O（n）．只需要n-1个同步消息。

基于车牌识别系统的卡口可达性网络构建

从交通可达性概念出发,对车牌识别卡口之间的可达性关系进行研究。针对卡口可达性的特点,对计算最短路径效果较好的A*算法进行改进,用于计算卡口间的可达关系,构建可达性网络。

基于插值原理的检查点技术波场重构与叠前逆时偏移

叠前逆时偏移等基于波场互相关原理的地球物理方法存在极大的计算与存储需求,因此采用合适的波场重构方法显得尤为重要.常规的随机边界法容易产生成像噪声,而有效边界法在三维情况仍难以实现,检查点技术具有内存要求小的特点,但存在较高的重算率,因此本文提出了插值原理的检查点技术波场重构方法.在满足Nyquist采样定理的前提下对相邻检查点间的波场进行规则抽样,将抽样波场作为插值节点,运用多项式插值算法重构任意时刻的波场,从而避免优化检查点技术反复递推造成的计算效率问题.数值实验表明:插值检查点重构算法能有效的恢复波场,其中三次样条插值重构精度最高,而牛顿法插值法计算代价较小适合于快速重构.经Sigsbee模型的叠前逆时偏移证明了插值算法的可行性,并且极大的提高了波场重构的计算效率.三维模型分析得出在增加少量存储的情况下插值重构法的重算率大幅度降低,存储量减少为有效边界法的7.1%,对于三维尺度的叠前逆时偏移有实际意义.

最大团的容错节点分配算法设计

内存检查点是当前最流行的容错技术之一,它通过对节点的分组来保存和恢复工作状态。但是,内存检测点技术的弊端之一便是不能有多个节点在同一分组中同时失效,否则整个系统便不能恢复。根据超级计算机的计算节点网络拓扑结构,提出了一种新的节点分配模型,对当前的分组方式做出了很大改进,实验结果表明,相对于传统分组方式,改进的节点分配模型使同组中多个节点同时出错的概率得到了降低,从而使得全系统恢复的开销相应减少了许多。

一种高效的协调式检查点算法

为降低设置检查点的开销,提出一种高效的异步存储非阻塞协调式检查点算法。该算法允许多个进程并发地在进程状态信息量较小时设置检查点,只在稳固存储器空闲时进行异步存储,并可同时进行检查点设置及进程执行。实验结果表明,该算法能降低设置检查点的开销,提高系统性能。

基于随机森林的流处理检查点性能预测

物联网(IoT)的发展引起流数据在数据量和数据类型两方面不断增长。由于实时处理场景的不断增加和基于经验知识的配置策略存在缺陷,流处理检查点配置策略面临着巨大的挑战,如费事费力,易导致系统异常等。为解决这些挑战,该文提出基于回归算法的检查点性能预测方法。该方法首先分析了影响检查点性能的6种特征,然后将训练集的特征向量输入到随机森林回归算法中进行训练,最后,使用训练好的算法对测试数据集进行预测。实验结果表明,与其它机器学习算法相比,随机森林回归算法在CPU密集型基准测试,内存密集型基准测试和网络密集型基准测试上针对检查点性能的预测具有误差低,准确率高和运行高效的优点。

远程测试系统数据不一致性检测算法的研究

结合远程测试系统的网络化和数据库分布式强的特点,提出数据库中数据冗余和物理分布所带来的问题——数据库中数据的不一致性。对数据的不一致性检测算法进行研究,分析常用的检查点算法,对检查点算法进行改进,由测试站点主动发送测试信息,以减少系统的通信开销,并在远程测试数据库系统中加以实现。最后,对这种改进的算法进行了总结。

ARIES算法在PostgreSQL中的实现

通过现有的PostgreSQL的恢复算法和ARIES算法的比较,说明采用ARIES算法来改进PostgreSQL的必要性,并在分析现有的PostgreSQL与恢复相关的几个实现策略上,介绍为采用ARIES算法而设计的主要数据结构以及如何改进事务恢复管理器以便支持ARIES算法的事务基本操作和恢复管理的实现流程。这样比较显著地提高了PostgreSQL的事务处理能力。