分布式系统的时间同步容错机制研究

网络化计算和分布式应用,对计算机系统的时间同步精度要求越来越高,高精密时间同步是分布式控制系统一切应用的基础.分布式系统必须建立统一的时间服务系统或时间服务器,以实现系统的时间统一.从时间同步着手,分析了时间同步技术——网络时间协议(NTP)和直接连接时间技术,研究了分布式系统时间同步技术及时间同步容错策略,给出了误差估算方法,并将滑动窗口演算法应用于时间同步容错策略,提出并得到时间校正值的算法,并对同步结果进行了分析.     

分布式系统的时间同步容错机制研究

网络化计算和分布式应用,对计算机系统的时间同步精度要求越来越高,高精密时间同步是分布式控制系统一切应用的基础。分布式系统必须建立统一的时间服务系统或时间服务器,以实现系统的时间统一。从时间同步着手,分析了时间同步技术——网络时间协议（NTP）和直接连接时间技术,研究了分布式系统时间同步技术及时间同步容错策略,给出了误差估算方法,并将滑动窗口演算法应用于时间同步容错策略,提出并得到时间校正值的算法,并对同步结果进行了分析。     

基于CORBA的分布式系统自适应容错模型的研究

一、引言分布式系统需要可靠性保证,例如在线支付系统对安全性提出了很高的要求。因此,分布式系统必须提供可靠性机制,支持关键业务。容错技术是分布式系统运行过程中可靠性保证的重要手段,冗余资源是实现容错的根本保证。单一的容错策略仅适用于特定的应用和特定的系统,无法适应系统状态的动态变化,支持广泛的分布式应用。系统的容错模型应该能够智能地根据外部运行环境的变化,选择合适的容错策略,以便在保证系统可靠性的前提下提高系统资源利用率。自适应容错可以在分布式系统中的各个层次中实现。基于操作系统的自适应容错强烈地依赖于特定的操作系统,系统可移植性差;而在应用程序中实现自适应容错又加重了开     

基于EDF的分布式系统实时容错调度算法

将分布式系统的任务分配算法与处理器局部调度算法相结合，提出一种主动备份的、基于EDF的分布式系统实时容错调度算法，其特点是主／副版本执行时间可以重叠。给出了该调度算法的任务集可调度的充分条件、任务集可调度所需最小处理器个数的计算方法。模拟结果比较了主动备份容错调度算法与被动备份容错调度算法，结果表明卞动备份算法效率更优。     

基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

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

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

分布式系统的时间同步算法研究及应用

实现分布式系统时间同步的方法有两种：一是将外部时间基准引入分布式系统的绝对时间同步,二是仅在分布式系统内部使用算法实现同步的相对时间同步。本文详细讨论了适用于局域网的各种时间同步算法,并对部分算法的应用结果进行了分析。     

分布式系统时钟同步设计与实现

时钟同步是分布式系统的核心技术之一，考虑到分布式系统的可扩展性及同步精度要求，提出了基于GPS与NTP的混合同步方案解决系统时间同步问题，并对其原理与实现进行了阐述。     

基于Web服务的数据同步机制的研究与应用

在大型分布式信息系统中，各个子系统并非同时集成，在其投人运行时，存在与信息系统数据不一致的问题；或者，分布式系统在运行一段时期以后，该系统中各个子系统间的数据就可能出现差异。文中针对分布式系统中的数据缺乏一致性和同步性的问题，提出了一种基于Web服务的同步策略，论述了该同步策略的实现机制，介绍了该同步机制的触发方式以及同步信息的结构和传输算法。     

基于RTEthernet改进的时钟同步算法

以太网其庞大的网络系统在复杂的环境中存在网络链路延迟,节点时钟的漂移,同步能力差等问题。通过研究RTEthernet协议的起源和工作原理,考虑到影响实时以太网时间同步精密度的时钟拜占庭故障、网络传输延迟和漂移率等三个因素,建立了符合RTEthernet协议的通信模型。对FTA时钟同步算法在故障下时钟同步精密度损失率提升较少的问题进行了研究,引入了滑动窗口技术,提出了容错滑动窗口（Fault-Tolerant Sliding Window, FTSW）算法。容错滑动窗口算法能进一步提高分布式系统在进行时钟同步是对故障节点的容错能力。最后,使用CANoe仿真工具对FTSW算法进行仿真验证, FTSW算法的容错性优于FTA时钟同步算法算法,且在系统（七个节点）中存在两个拜占庭故障的情况下,同步后的精密度损失率降低了7.1%。     

Integrating External and Internal Clock Synchronization

We address the problem of how to integrate fault-tolerant external and internal clock synchronization. In this paper we propose a new external/internal clock synchronization algorithm which provides both external and internal clock synchronization for as long as a majority of the reference time servers (servers with access to reference time) stay correct. When half or more of the reference time servers are faulty, the algorithm degrades to a fault-tolerant internal clock synchronization algorithm. We prove that at least 2 F+1 reference time servers are necessary for achieving external clock synchronization when up to F reference time servers can suffer arbitrary failures, thus the proposed algorithm provides maximum fault-tolerance. In this paper we also derive lower bounds for the best maximum external deviation achievable in standard mode and the best drift rate achievable in degraded mode. Our algorithm is optimal with respect to these two bounds: (1) the maximum external deviation is optimal in standard mode, and (2) the drift rate of the clocks is optimal in standard and degraded mode.     

FlexRay时钟同步分析

描述FlexRay网络的基本特点及FlexRay网络时钟同步算法的具体过程,介绍FlexRay网络的容错中间点算法,提出时钟同步算法的数学模型,并对数学模型进行分析。从理论上说明FlexRay时钟同步算法具有较强的容错性和适用性。     

基于PVM的准同步检查点设置方法

检查点是并行系统中实现容错的重要手段,同步检查点方法已广泛应用在工作站机群系统中。PVM所提供的消息传递机制支持高效的异构网络计算,但不支持客错功能。为了降低同步检查点设置的时间开销,提出了一种基于PVM的准同步检查点设置方法,它吸取了同步检查点方法的优点,又通过消息记录方式实现各节点间独立进行状态保存,大大降低了检查点的同步开销,提高了检查点操作效率,该方法在PVM环境下得以实现,实验结果表明所提出的方法具有较好的客错性能。     

A clock synchronization algorithm for the performance analysis of multicomputer systems

The paper deals with the implementation of global time in multicomputer systems. After a formalization of the synchronization problem, techniques to estimate the synchronization delay and to compensate the drift error are proposed. Then SYNC_WAVE, a clock synchronization algorithm where the values of a reference clock are diffused in a wave-like manner, is described. SYNC_WAVE has no provision for fault-tolerance and is specially designed to introduce low CPU and communication overhead, in order to support performance analysis applications efficiently. An implementation of the devised algorithm in a transputer-based system is presented, showing the accuracy results obtained. Finally SYNC_WAVE is compared to other synchronization algorithms and several of its possible applications are suggested.     

An integrated security-aware job scheduling strategy for large-scale computational grids

All existing fault-tolerance job scheduling algorithms for computational grids were proposed under the assumption that all sites apply the same fault-tolerance strategy. They all ignored that each grid site may have its own fault-tolerance strategy because each site is itself an autonomous domain. In fact, it is very common that there are multiple fault-tolerance strategies adopted at the same time in a large-scale computational grid. Various fault-tolerance strategies may have different hardware and software requirements. For instance, if a grid site employs the job checkpointing mechanism, each computation node must have the following ability. Periodically, the computational node transmits the transient state of the job execution to the server. If a job fails, it will migrate to another computational node and resume from the last stored checkpoint. Therefore, in this paper we propose a genetic algorithm for job scheduling to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. We assume that the system supports four kinds fault-tolerance mechanisms, including the job retry, the job migration without checkpointing, the job migration with checkpointing, and the job replication mechanisms. Because each fault-tolerance mechanism has different requirements for gene encoding, we also propose a new chromosome encoding approach to integrate the four kinds of mechanisms in a chromosome. The risk nature of the grid environment is also taken into account in the algorithm. The risk relationship between jobs and nodes are defined by the security demand and the trust level. Simulation results show that our algorithm has shorter makespan and more excellent efficiencies on improving the job failure rate than the Min–Min and sufferage algorithms.     

基于CORBA的分布对象容错机制研究与实现

一、引言目前,以CORBA为代表的分布对象计算技术已日趋成熟,越来越多的分布式应用系统利用CORBA提供的标准服务和协议来实现。基于CORBA的新一代的分布式系统,如分布式实时控制系统、在线支付系统和股票交易系统,需要可靠性保证。容错技术是分布式系统运行过程中可靠性保证的重要手段,可以在分布式系统的每一个层次实现,利用底层的CORBA基础设施提供容错机制具有显著的优势,既能够避免系统层为支持容错而做的巨大改变,又能够简化应用软件的设计。因此,容错CORBA已经成为国外CORBA研究的重     

Java服务主动容错模型分析与评估

Java服务已成为支撑关键业务的业务服务,其可用性成为关键业务系统是否能持续提供服务的关键。采用主动容错技术可提高Java服务的可用性,建立Java服务的主动容错模型,便于分析和评估主动容错技术的有效性。通过模型分析与仿真实验的方法比较了采用Rejuvenation策略与不采用Rejuvenation策略的容错效果,通过分析评估得出,采用主动容错技术将有效改善Java服务的可用性,如果合理选择实施软件Rejuvenation策略的时间点,则可以取得更好的容错效果。     

自动信任协商中信任证存储策略研究

分布式信任证存储策略存在单点失效及容错性差等问题,可能导致信任证丢失.为此,提出一种改进的分布式存储策略.该策略以分布式存储策略为基础,运用已有的数据结构支持信任证存储策略的设计.基于资源冗余的思想,采用多信任证副本和信任证恢复机制,提升系统容错能力.实验结果表明,该存储策略具有较好存储均衡性.     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.