纠错码拜占庭容错Quorum中错误检测机制

摘要在大规模存储系统中，拜占庭存储节点的容错显得越来越重要。传统拜占庭Quorum通过复制可以容忍拜占庭失效，但是它们有两个主要缺点：低的存储空间利用率和静态quorum参数。我们提出纠错码拜占庭容错Quorum（Erasure-code Byzantine Fault-tolerance Quorum, E-BFQ），E-BFQ采用纠错码作为冗余策略，可以提供高可靠性，同时比复制占用更少存储空间。通过客户端读／写操作和管理器诊断操作，E-BFQ可以检测拜占庭节点，动态调整系统规模和故障闽值。结果显示本文方法可以达到动态调整的目的。     

一种基于特权分级的quorum系统构造方案*

为解决现有的quorum系统节点没有差异、数据读取延迟较大、存储利用率低等缺陷,提出了一种新的基于特权分级的quorum系统。该系统借助代理动态调整各quorum,并按数据存储时段将各节点划分为不同的等级,此外还设计了相应的数据读写协议。通过系统性能分析表明,该方案具有读写高效性、存储可靠性及易于扩展等优点。     

基于Quorum系统的分布式访问控制框架研究

从通用访问控制系统出发,提出以quorum系统来设计访问控制框架,给出了基于互斥协议的quorum分布式访问控制系统(MQ-DACS),以在保持高效率的情况下,提高访问控制决策的稳定性和安全性。进一步分析了在系统结点不可靠的环境中,系统能并行执行的访问控制容量同系统可用性之间的关系,并给出了最佳方案的选取依据。     

基于非完备性测试的一种分布式计算机系统诊断算法的设计

利用现有的商用并行、分布式计算机系统本身所固有的冗余可以实现低成本的容错。为了提高整个分布式计算机系统的可靠性,将系统中的故障结点与正确结点隔离至关重要。文章提出了一个有效的分布式系统级故障诊断算法：在利用系统中各结点机有限的故障检测能力的基础上,将所有的故障结点从系统中隔离,并测试了该算法对系统性能的影响。     

基于四叉树多层次感知数据融合的无线传感网络路由协议的研究

为有效减少网络中冗余信息传输,提出一种基于四叉树均匀分簇的无线传感网络路由协议----QUCRP。首先对监测区域按四叉树进行网格划分,并对划分的簇及簇群进行四叉树编码;接着从节点的剩余能量、网格中心距离、节点的功率等方面考虑,设计簇首选举算法;最后采用多层次的数据融合策略,对感知数据进行逐层融合并转发,有效降低数据传输能量消耗。仿真实验表明,QUCRP路由协议有效降低了冗余信息传输,延长了网络的生命周期。     

微信分布式数据存储协议对比

分布式系统是网络化的计算机系统,海量数据的互联网应用只能通过分布式系统协调大量计算机来支撑.微信后台存储大量使用了分布式数据存储方式的NoSQL集群.存储设备出现异常是必然,分布式系统通过多节点分布及冗余,避免个别异常节点影响到系统的正常服务,同时提供平行扩展能力.微信自研的分布式存储在发展的不同阶段,分别依赖过Paxos和Quorum两种方案维护一致性.Paxos和Quorum也是互联网企业主要使用的分布式协议.     

OXVoD：一个基于分层结构的P2P视频点播系统

可扩展性和高播放连续度是视频点播系统大规模应用的关键。提出了一个分层结构的P2P点播系统,融合了Distributed Hash Table（DHT）的精确高效和Gossip协议的简单实用。该系统上层结点为下层结点提供下载服务,有效均衡负载。提出了一种数据调度策略,通过在基于Gossip协议数据可用信息交互过程中添加少量本地信息,帮助下载者选择最优下载源,提高系统播放连续度。仿真实验表明,OXVoD可以在服务器负载稳定的情况下,保证99%以上的结点正常加入系统,并获得96%以上的播放连续度。     

局域网中虚拟路由器集群的设计与实现

VRRP协议使一组路由器组成一台虚拟路由器,局域网终端设备将访问外部网络的数据发送给虚拟路由器。而数据的实际转发则由VRRP备用组的活动路由器(Master)来完成,一旦Master出现故障,备用组中的备用路由器就按优先级选举产生新的Master接替故障设备承担的工作,利用VRRP协议定义的这种机制就能实现局域网络的路由冗余和负载均衡,保证局域网络运行的可靠性。     

基于邻结点表的MANET网络路由协议

本文先分析了当前MANET系统中的路由协议，提出了一种基于邻结点表的路由协议算法，利用邻结点信息，提高了路由的自我维护能力。最后通过仿真实验，验证了该算法的有效性。     

实时多任务软件系统的可靠性模型

在一个实时多结点，多任务系统中，软件系统的故障是由多种原因引起的，比如，某一个结点上一个任务模块的设计缺陷或者瞬时故障；任务执行超过截止时间，结点间的通讯故障或者通讯超时等原因。基于上述特点，本文根据程序模块的故障概率和结点间通讯关系，提出了一个实时多任务系统的可靠性评价模型。     

Synchronous Byzantine quorum systems

Summary. Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns. Received: June 1998 / Accepted: August 1999     

Access cost for asynchronous Byzantine quorum systems

Summary. Quorum systems have been used to implement many coordination problems in distributed systems. In this paper, we study the cost of accessing quorums in asynchronous systems. We formally define the asynchronous access cost of quorum systems and argue that the asynchronous access cost and not the size of a quorum is the right measure of message complexity of protocols using quorums in asynchronous systems. We show that previous quorum systems proposed in the literature have a very high asynchronous access cost. We propose a reformulation of the definition of Byzantine quorum systems that captures the requirement for non-blocking access to quorums in asynchronous systems. We present new Byzantine quorum systems with low asynchronous access cost whose other performance parameters match those of the best Byzantine quorum systems proposed in the literature. In particular, we present a construction for the disjoint failure pattern that outperforms previously proposed systems for that pattern. Received: September 1999 / Accepted: September 2000     

Probabilistic quorums for dynamic systems

A quorum system is a set of sets such that every two sets in the quorum system intersect. Quorum systems are well known building blocks for maintaining information in a distributed system while providing high availability and good load balance. Probabilistic Quorum Systems (PQS) are variants of quorum systems that relax the strict intersection requirement. They are particularly attractive for large scale systems due to their simplicity and highly efficient availability—load balance tradeoff. We introduce scalable techniques that maintain a PQS in a highly decentralized and highly dynamic setting. We address two challenges. First we show how PQS can be realized efficiently even when each process maintains knowledge of only a constant number of other members. Second, we provide algorithms that adaptively evolve the quorums to adjust to the changes in the system caused by processes leaving and joining the system over time.     

Crumbling walls: a class of practical and efficient quorum systems

Summary.  A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication and dissemination of information. In this paper we introduce a general class of quorum systems called Crumbling Walls and study its properties. The elements (processors) of a wall are logically arranged in rows of varying widths. A quorum in a wall is the union of one full row and a representative from every row below the full row. This class considerably generalizes a number of known quorum system constructions. The best crumbling wall is the CWlog quorum system. It has small quorums, of size O(lg n), and structural simplicity. The CWlog has optimal availability and optimal load among systems with such small quorum size. It manifests its high quality for all universe sizes, so it is a good choice not only for systems with thousands or millions of processors but also for systems with as few as 3 or 5 processors. Moreover, our analysis shows that the availability will increase and the load will decrease at the optimal rates as the system increases in size. Received: August 1995 / Accepted: August 1996     

Geographic Quorum System Approximations

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in the plane (representing servers) into quorums (i.e., clusters) of size k. The distance between a point p and a cluster C is the Euclidean distance between p and the site in C that is the farthest from p. We present a near linear time constant-factor approximation algorithm for partitioning X into clusters, such that the maximal distance between a point in the underlying region and its closest cluster is minimized. Next, we describe a data structure for answering (approximately) nearest-neighbor queries on such a clustering. Finally, we study the problem of partitioning into clusters with an additional load-balancing requirement.     

分布式系统数据复制协议的研究

数据复制正在并行信息系统的设计中起着越来越重要的作用.特别地,为了提高性能和可用性,对集群体系结构的广泛使用经常要求复制数据.然而,维持不同拷贝的一致性带来严重的可伸缩性问题.为了克服这个局限性,基于表决的协议经常被作为一种缩减复制的总开销的方法.为了更好理解它们在实际中的性能,分析了几种表决算法,结果是基于表决的复制协议表现出不错的性能.测试表明ROWA-A(read-one/write-all-available)协议对于需要大量数据复制的应用是最好的选择.     

Refined quorum systems

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing, at the same time, optimal resilience, as well as optimal best-case complexity. We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: first class quorums are also second class quorums, themselves being also third class quorums. First class quorums have large intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming a general adversary structure, and this basically allows algorithms relying on refined quorum systems to relax the assumption of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two new optimal Byzantine-resilient distributed object implementations: an atomic storage and a consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here. Each of our algorithms is representative of a different class of architectures, highlighting the generality of the refined quorum abstraction.     

Access control and signatures via quorum secret sharing

We suggest a method of controlling the access to a secure database via quorum systems. A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We propose a separation between access servers, which are protected and trustworthy, but may be outdated, and the data servers, which may all be compromised. The main paradigm is that only the servers in a complete quorum can collectively grant (or revoke) access permission. The method we suggest ensures that, after authorization is revoked, a cheating user Alice will not be able to access the data even if many access servers still consider her authorized and even if the complete raw database is available to her. The method has a low overhead in terms of communication and computation. It can also be converted into a distributed system for issuing secure signatures. An important building block in our method is the use of secret sharing schemes that realize the access structures of quorum systems. We provide several efficient constructions of such schemes which may be of interest in their own right     

Dynamic grid quorum: a reconfigurable grid quorum and its power optimization algorithm

Power-saving has become a central issue for well-configured SOC platforms. In particular, as a high percentage of the total energy is used by the storage systems, the cost effectiveness of data management is equally as important as reliability and availability. To address this issue, we propose the dynamic grid quorum as a method for reducing the power consumption of large-scale distributed storage systems. The basic principle of our approach is to skew the workload toward a small number of quorums. This can be realized using the following three techniques. First, our system allows reconfiguration by exchanging nodes without any data migration, so that high-capacity nodes can be reallocated to busier quorums. Second, for more effective skewing of the workload, we introduce the notion of dual allocation, which makes it possible to consider two distinct allocations in the same grid for write and read quorums. Finally, we present an optimization algorithm to find a pair of a strategy and an allocation of nodes, which minimizes power for a given system setting and its workload. We also demonstrate that the dynamic grid quorum saves, on average, 14–25% energy compared with static configurations, when the intensity of the total workload changes.