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     

Byzantine quorum systems

Summary. Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first study of quorum system requirements and constructions that ensure data availability and consistency despite these failures. We also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server. For services subject to arbitrary failures, we demonstrate quorum systems over servers with a load of , thus meeting the lower bound on load for benignly fault-tolerant quorum systems. We explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures. Received: October 1996 / Accepted June 1998     

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.     

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

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

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     

Probabilistic Quorum Systems

We initiate the study of probabilistic quorum systems, a technique for providing consistency of replicated data with high levels of assurance despite the failure of data servers. We show that this technique offers effective load reduction on servers and high availability. We explore probabilistic quorum systems both for services tolerant of benign server failures and for services tolerant of arbitrary (Byzantine) ones. We also prove bounds on the server load that can be achieved with these techniques.     

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.     

Update propagation strategies to improve freshness in lazy master replicated databases

Many distributed database applications need to replicate data to improve data availability and query response time. The two-phase commit protocol guarantees mutual consistency of replicated data but does not provide good performance. Lazy replication has been used as an alternative solution in several types of applications such as on-line financial transactions and telecommunication systems. In this case, mutual consistency is relaxed and the concept of freshness is used to measure the deviation between replica copies. In this paper, we propose two update propagation strategies that improve freshness. Both of them use immediate propagation: updates to a primary copy are propagated towards a slave node as soon as they are detected at the master node without waiting for the commitment of the update transaction. Our performance study shows that our strategies can improve data freshness by up to five times compared with the deferred approach. Received April 24, 1998 / Revised June 7, 1999     

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     

Failure detection and consensus in the crash-recovery model

Summary. We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those with no failures or failure detector mistakes. In such runs, consensus is achieved within time and with 4 n messages, where is the maximum message delay and n is the number of processes in the system. Received: May 1998 / Accepted: November 1999     

Synchronization support and group-membership services for reliable distributed multimedia applications

We describe a collection of algorithms designed to support reliable synchronization and group membership services for distributed multimedia applications. In particular, we consider those applications that require interactivity, isochronous rendering of multimedia data, and high reliability. We show that the algorithms we propose (i) provide reliable support for the synchronization of multimedia data streams, despite the occurrence of possible communication failures, (ii) maintain a consistent view of the relative group membership of all the nonfaulty application components, (iii) guarantee time-bounded delay of component failure detection and join, and (iv) meet effectively possible scalability requirements of the applications.     

Transversal merge operation: a nondominated coterie construction method for distributed mutual exclusion

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.     

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.     

A self-stabilizing quorum-based protocol for maxima computing

The goal of decentralized consensus protocols is to exchange information among nodes so that each node acquires the information held by every other node in the system. This paper presents a quorum-based, self-stabilizing maxima finding protocol which is based on a decentralized consensus protocol. The protocol exchanges information with less delay than existing ring-based, self-stablizing protocols. Furthermore, quorums can be composed, and the resulting composite quorums can be used to efficiently obtain a solution for any internetwork. Received: October 1999 / Accepted: June 2001     

Performing tasks on synchronous restartable message-passing processors

Summary. This work considers the problem of performing t tasks in a distributed system of p fault-prone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. The solutions presented here are for the model of computation that abstracts a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of stop-failures and does not allow restarts. Its available processor steps (work) complexity is and its message complexity is . Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p =t and largef, it achieves better work complexity. This algorithm is used as the basis for another algorithm that tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem that efficiently deals with processor restarts. Its available processor steps is , and its message complexity is , wheref is the total number of failures. Received: October 1998 / Accepted: September 2000     

Quorum-based power-saving multicast protocols in the asynchronous ad hoc network

The asynchronous PS (Power-Saving) unicast protocol was designed for two PS wireless hosts to transmit the unicast message in the ad hoc network even their clocks are asynchronous. However, as regard to transmit a multicast message among more than two PS hosts, the protocol could not guarantee that all PS hosts can wake up at the same time. Some PS hosts may be in the PS mode when the multicast message is transmitted. Thus, the multicast message should be retransmitted again and again until all PS hosts receive the message. It will increase the energy consumption and the usage of the bandwidth. In this paper, we propose quorum-based PS multicast protocols for PS hosts to transmit multicast messages in the asynchronous ad hoc network. In those protocols, PS hosts use quorums to indicate their wakeup patterns. We introduce the rotation m-closure property to guarantee that m different quorums have the intersection even quorums are rotated due to asynchronous clocks. Thus, m PS hosts adopting m quorums satisfying the rotation m-closure property could wake up simultaneously and receive the multicast message even their clocks are asynchronous. We propose two quorum systems named the uniform k-arbiter and the CRT (Chinese Remainder Theorem) quorum system, which satisfy the rotation m-closure property. As shown in our analysis results, our quorum-based PS multicast protocols adopting those quorum systems can save more energy to transmit multicast messages.     

Refinement-based formal verification with heterogeneous timing

In this paper we propose a refinement-based technique to formally verify data transfer in a heterogeneous timing framework. Novel data transfer models are proposed to represent data communication between two locally independent clock domains via an asynchronous handshake environment. As a case study, we apply our technique to automatically verify data transfer in a previously published architecture for globally asynchronous locally synchronous on-chip systems. In this case study, we find several race conditions, hazards, and other dangers that were not mentioned in the original publication, and we find additional delay constraints that avoid some of the detected dangers. Published online: 17 December 2002     

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     

An asymptotically optimal multiversion B-tree

In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others.     

Asynchronous group mutual exclusion

Abstract. Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in some applications such as Computer Supported Cooperative Work (CSCW) we have found it necessary to impose mutual exclusion on different groups of processes in accessing a resource, while allowing processes of the same group to share the resource. To our knowledge, no such design issue has been previously raised in the literature. In this paper we address this issue by presenting a new problem, called Congenial Talking Philosophers, to model group mutual exclusion. We also propose several criteria to evaluate solutions of the problem and to measure their performance. Finally, we provide an efficient and highly concurrent distributed algorithm for the problem in a shared-memory model where processes communicate by reading from and writing to shared variables. The distributed algorithm meets the proposed criteria, and has performance similar to some naive but centralized solutions to the problem. Received: November 1998 / Accepted: April 2000