入侵容忍数据库的选举算法和同步方案设计

基于冗余的入侵容忍数据库是由多个异构数据库服务器组成的,通过增加冗余单元实现数据库的可生存性和可用性,但是冗余会引起系统性能下降.为提高系统性能,必须解决选举和数据库同步问题,这需要有效的算法及复杂周密的同步协议来实现.给出了多种可行的选举算法和一种动态同步方案,能够很好地解决数据库之间的选举和同步问题.     

多复制服务器间无阻塞的数据更新

在Client/Server系统中,服务器的可用性是提高整个系统可用性的关键,采用多复制服务器是提高系统可用性的最有希望的手段.但是,复制数据更新过程中的阻塞问题是整个系统性能的一个瓶颈.本文提出一种无阻塞的多服务器独立提交的复制数据更新方法,对于因失效不能完成更新的服务器采用协调机制使其达到相同的最终状态.     

A paracasting model for concurrent access to replicated Internet content

In this paper, we develop a model to study how to effectively download a document from a set of replicated servers. We propose a generalized application-layer anycasting protocol, known as paracasting, to advocate concurrent access of a subset of replicated servers to cooperatively satisfy a client's request. Each participating server satisfies the request in part by transmitting a subset of the requested file to the client. The client can recover the complete file when different parts of the file sent from the participating servers are received. This model allows us to estimate the average time to download a file from the set of homogeneous replicated servers, and the request blocking probability when each server can accept and serve a finite number of concurrent requests. Our results show that the file download time drops when a request is served concurrently by a larger number of homogeneous replicated servers, although the performance improvement quickly saturates when the number of servers increases. If the total number of requests that a server can handle simultaneously is finite, the request blocking probability increases with the number of replicated servers used to serve a request concurrently. Therefore, paracasting is effective when a small number of servers, say, up to four, are used to serve a request concurrently.     

改进的Michael Merrit投票协议

互联网的快速发展使得网上投票成为可能。Michael Merrit协议是一种无须中央制表机构的投票系统，它有两个缺陷：选票能被复制，某个人将比其他人更早得知选票结果。该文提出了对MichaelMerrit协议的改进，克服了这两个缺陷。改进后的协议将适用于小型的无须中央制表机构的投票系统。     

A Case Study of Load Sharing Based on Popularity in Distributed VoD Systems

In our research, we consider a distributed video-on-demand (VoD) system in which only the most popular videos are replicated in all the servers, whereas the rest of them are distributed through the system following some allocation scheme. In this paper, we present an algorithm to efficiently share the load in such a system and an analytical model that captures the performance of this algorithm, which we validate through simulations. One novelty in our work is that our analytical model lets us relate popularity and partial replication of some of the videos and to predict the user waiting time. We exploit such relationships to assist the system designer to select the size of the servers and network, the optimal number of servers to maintain short waiting time and to predict when the network encounters bottleneck     

The Raid distributed database system

Raid, a robust and adaptable distributed database system for transaction processing, is described. Raid is a message-passing system, with server processes on each site. The servers manage concurrent processing, consistent replicated copies during site failures and atomic distributed commitment. A high-level, layered communications package provides a clean, location-independent interface between servers. The latest design of the communications package delivers messages via shared memory in a high-performance configuration in which several servers are linked into a single process. Raid provides the infrastructure to experimentally investigate various methods for supporting reliable distributed transaction processing. Measurements on transaction processing time and server CPU time are presented. Data and conclusions of experiments in three categories are also presented: communications software, consistent replicated copy control during site failures, and concurrent distributed checkpointing. A software tool for the evaluation of transaction processing algorithms in an operating system kernel is proposed     

Intrusion-Tolerant Server Architecture for Survivable Services

Survivable systems are increasingly needed in a wide range of applications. As a step toward realizing survivable systems, this paper presents architecture of intrusion-tolerant servers. It is to deliver intended services transparently to the clients even when a computing node fails due to failures, intrusions, and other threats. In order to deliver only secure results to the client, we need an algorithm to decide agreement on results from replicated servers. For this purpose, a secure and practical decentralized voting algorithm for the architecture is proposed in the paper. Through the experiments on a test-bed, especially, for web services, the approach turned out very effective in terms of extra cost and considered to be able to cope with both confidentiality and integrity attacks.     

Intrusion-tolerant server architecture for survivable services

Survivable systems are increasingly needed in a wide range of applications. As a step toward realizing survivable systems, this paper presents architecture of intrusion-tolerant servers. It is to deliver intended services transparently to the clients even when a computing node fails due to failures, intrusions, and other threats. In order to deliver only secure results to the client, we need an algorithm to decide agreement on results from replicated servers. For this purpose, a secure and practical decentralized voting algorithm for the architecture is proposed in the paper. Through the experiments on a test-bed, especially, for web services, the approach turned out very effective in terms of extra cost and considered to be able to cope with both confidentiality and integrity attacks.     

拟态通用运行环境的框架设计

为实现信息系统安全防御的目的,针对动态异构冗余(DHR)架构设计拟态通用运行环境(MCOE)框架。以拟态化改造后功能等价的异构冗余信息系统应用程序,以及异构化的信息系统运行环境设施为对象,为N异构执行体构建面向服务请求的资源调度、分发、执行、表决、安全威胁清洗恢复以及管理的自动化运行支撑环境,提供拟态产品的分发、表决统一集成接口规范。在该框架中,服务请求主键驱动的N个异构执行体和MCOE分发、内部表决、外部表决、协同执行、管理5个服务器交互运行。仿真结果表明,该设计可有效抵御软硬件后门和漏洞引发的网络攻击。     

Fault detection for Byzantine quorum systems

In this paper, we explore techniques to detect Byzantine server failures in asynchronous replicated data services. Our goal is to detect arbitrary failures of data servers in a system where each client accesses the replicated data at only a subset (quorum) of servers in each operation. In such a system, some correct servers can be out-of-date after a write and can therefore, return values other than the most up-to-date value in response to a client's read request, thus complicating the task of determining the number of faulty servers in the system at any point in time. We initiate the study of detecting server failures in this context, and propose two statistical approaches for estimating the risk posed by faulty servers based on responses to read requests     

Task Allocation in a Multi-Server System

We consider a slotted queueing system with C servers (processors) that can handle tasks (jobs). Tasks arrive in batches of random size at the start of every slot. Any task can be executed by any server in one slot with success probability . If a task execution fails, then the task must be handled in some later time slot until it has been completed successfully. Tasks may be processed by several servers simultaneously. In that case, the task is completed successfully if the task execution is successful on at least one of the servers.We examine the impact of various allocation strategies on the mean number of tasks in the system and the mean response time of tasks. It is proven that both these performance measures are minimized by the strategy which always distributes the tasks over the servers as evenly as possible. Subsequently, we determine the distribution of the number of tasks in the system for a broad class of task allocation strategies, which includes the above optimal strategy as a special case. Some numerical experiments are performed to illustrate the performance characteristics of the various strategies.     

A dual-direction technique for fast file downloads with dynamic load balancing in the Cloud

File downloads make up a large percentage of the Internet traffic to satisfy various clients using distributed environments for their Cloud, Grid and Internet applications. In particular, the Cloud has become a popular data storage provider and users (individuals and corporates) are relying heavily on it to keep their data. Furthermore, most cloud data servers replicate their data storage infrastructures and servers at various sites to meet the overall high demands of their clients and increase availability. However, most of them do not use that replication to enhance the download performance per client. To make use of this redundancy and to enhance the download speed, we introduce a fast and efficient concurrent technique for downloading large files from replicated Cloud data servers and traditional FTP servers as well. The technique, DDFTP utilizes the availability of replicated files on distributed servers to enhance file download times through concurrent downloads of file blocks from opposite directions in the files. DDFTP does not require coordination between the servers and relies on the in-order and reliability features of TCP to provide fast file downloads. In addition, DDFTP offers efficient load balancing among multiple heterogeneous data servers with minimal overhead. As a result, we can maximize network utilization while maintaining efficient load balancing on dynamic environments where resources, current loads and operational properties vary dynamically. We implemented and evaluated DDFTP and experimentally demonstrated considerable performance gains for file downloads compared to other concurrent/parallel file/data download models.     

Coding-based replication schemes for distributed systems

Data is often replicated in distributed systems to improve availability and performance. This replication is expensive in terms of disk storage since the existing schemes generally require full files to be stored at each site. In this paper, we present schemes which significantly reduce the storage requirements in replication based systems. These schemes use the coding method suggested by Rabin to store replicated data. The first scheme that we present is a modification of the simple voting algorithm and its quorum requirements. We then show how some of the extensions of the voting algorithm can also be modified to get storage efficient schemes for managing such replication. We evaluate the availability offered by these schemes and show that the storage space required to achieve certain availability are significantly lower than the conventional schemes with full file replication. Since coding is used, these schemes also provide a high degree of data security     

Utility servers in charlotte

Most distributed operating systems are built with a kernel replicated in each machine that supports only basic interprocess communication (IPC) and process control. All other system services, such as memory management, file system, and name service, are distributed in a set of utility servers, which are ordinary processes (except perhaps for some privileges) residing at various machines. Design and implementation of such utility servers in distributed environments are far different from those in a centralized system. This paper presents our experience in building utility servers in Charlotte, a message-based distributed operating system running on a loosely-coupled multicomputer. Utility services in Charlotte are provided by server squads. Each member in a squad covers services to its own community. The squad as a whole co-operatively provides services to the entire system. These servers are designed with the goals of simplicity, efficiency and robustness. They are intended to support a multiprogramming system for the development of distributed algorithms and other distributed applications. We address several major issues in developing a utility server, including the server structure, the management of message buffers, deadlock, and the robustness of server processes. Several utility servers in the Charlotte system are discussed as real examples.     

Capacity of voting systems

Data replication is often used to increase the availability of data in a database system. Voting schemes can be used to manage this replicated data. The authors use a simple model to study the capacity of systems using voting schemes for data management. Capacity of a system is defined as the number of operations the system can perform successfully, on an average, per unit time. The capacity of a system using voting is examined and compared with the capacity of a system using a single node. It is shown that the maximum increase in capacity by the use of majority voting is bounded by 1/p, where p is the steady-state probability of a node being alive. It is also shown that for a system employing majority voting, if the reliability of nodes is high, increasing the number of nodes to more than three gives only a marginal increase in capacity. Similar analyses are performed for three other voting schemes     

Epidemic algorithms for replicated databases

We present a family of epidemic algorithms for maintaining replicated database systems. The algorithms are based on the causal delivery of log records where each record corresponds to one transaction instead of one operation. The first algorithm in this family is a pessimistic protocol that ensures serializability and guarantees strict executions. Since we expect the epidemic algorithms to be used in environments with low probability of conflicts among transactions, we develop a variant of the pessimistic algorithm which is optimistic in that transactions commit as soon as they terminate locally and inconsistencies are detected asynchronously as the effects of committed transactions propagate through the system. The last member of the family of epidemic algorithms is pessimistic and uses voting with quorums to resolve conflicts and improve transaction response time. A simulation study evaluates the performance of the protocols.     

大规模MPI 并行计算的可扩展三模冗余容错机制

随着系统规模的扩大,并行计算的性能不断提高,但可靠性却也在不断下降,因此需要采用某种容错机制来容忍或恢复硬件故障和数据错误.目前常用的容错机制Checkpoint/Restart和多模冗余均引入了额外的开销,这些开销均在某种程度上制约了并行计算的可扩展性.因此,在高性能计算需求不断增长的今天,可扩展容错机制的设计显得尤为迫切和重要.以三模冗余(triple modular redundancy,简称TMR)为典型案例,描述了传统TMR在大规模MPI 并行计算上的实现方法,分析了该机制所面临的实际问题,进而指出传统TMR制约了并行计算的扩展.根据该技术所面临的问题,设计了可扩展三模冗余(scalable triple modular redundancy,简称STMR),并进一步验证了其有效性和可扩展性.该机制不仅能够处理Checkpoint/Restart针对的fail-stop故障,还能够解决绝大部分硬件不能直接感知的数据错误.最后,借用BlueGene/L的系统参数进行模拟,预测当系统规模增大时,在分别采用TMR和STMR的情况下并行计算可扩展性的变化,结果进一步验证了STMR是可扩展的容错机制.     

ESD系统在催化装置的应用及改进

SORALCHIN炼油厂ESD系统——TS3000完成装置和机组工艺参数的监控、联锁保护和机组的防喘振控制，该系统为三重冗余容错系统（TMR）．这种三取二表决系统为催化装置和机组运行提供完善的控制和联锁保护。同时针对系统出现的问题．如系统死机、24VDC电源、主风低流量信号切除等问题提出了规避措施和改进方案。     

Stochastic Petri net analysis of a replicated file system

The authors present a stochastic Petri net model of a replicated file system in a distributed environment where replicated files reside on different hosts and a voting algorithm is used to maintain consistency. Witnesses, which simply record the status of the file but contain no data, can be used in addition to or in place of files to reduce overhead. A model sufficiently detailed to include file status (current or out-of-date) as well as failure and repair of hosts where copies or witnesses reside, is presented. The number of copies and witnesses is not fixed, but is a parameter of the model. Two different majority protocols are examined     

Retrieval scheduling for collaborative multimedia presentations

The single-system approach is no longer sufficient to handle the load on popular Internet servers, especially for those offering extensive multimedia content. Such services have to be replicated to enhance their availability, performance, and reliability. In a highly replicated and available environment, server selection is an important issue. In this paper, we propose an application-layer broker (ALB) for this purpose. ALB employs a content-based, client-centric approach to negotiate with the servers and to identify the best server for the requested objects. ALB aims to maximize client buffer utilization in order to efficiently handle dynamic user interactions such as skip, reverse presentation, go back in time. We also present details of a collaborative multimedia presentation platform that we have developed based on ALB.