Skip to main content
main-content

Über dieses Buch

Data replication by employing quorum systems is an important concept to improve operation availability on data objects in distributed systems that have strong data consistency demands. These data replication schemes must be modeled and carefully evaluated with respect to different quality measures. Christian Storm addresses the former by a uniform data replication scheme specification method and realizes the latter by a comprehensive approach to the analytical evaluation of quorum-based data replication schemes. The system model allows to evaluate operation availability and other quality measures for the write as well as for the read operation.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
In the past decades, computer systems such as banking cash machine networks, networked business systems, or Internet services have become pervasive and gained significant importance in our daily private and business life. The flip side of the coin is computer systems not only having caused economic damage but also failures that lead to loss of life [Neumann, 1994]. Thus, a key concern is the trustworthiness of such systems with respect to safety, security, privacy, performance, correctness, and availability. In particular availability and correctness as the probability that a system is operable at a given time and provides the intended service is of utmost importance.
Christian Storm

2. Fault Tolerance in Distributed Computing

Abstract
A distributed system consists of several independent processing components that interact with each other via an interconnecting communication link network consisting of communication components. Distributed computing refers to the algorithmic controlling of the distributed system’s processing components by means of a distributed program in order to reach a collective goal, that is, to provide a certain service. Unfortunately, the components of literally every system are naturally imperfect and therefore prone to failures that may render the system unable to provide the service. In order to be able to tolerate the failure of some components, that is, to keep the service available despite these failures, the system must be equipped with redundancy in space and time. The former refers to redundant components that take over the part played by failed components. The latter refers to the additional overhead required to manage these components. Fault-tolerant distributed computing refers to the algorithmic controlling of the distributed system’s components to provide the desired service despite the presence of certain failures in the system by exploiting redundancy in space and time.
Christian Storm

3. Specification of Quorum Systems

Abstract
Quorum-based data replication schemes are specified via two sets of subsets of the set of processes: The write quorum set’s quorums are used to perform write operations and the read quorum set’s quorums are used to perform read operations. These two sets are constructed such that every two write quorums intersect in at least one process and every write quorum intersects with every read quorum in at least one process. Two read quorums need not to intersect. The deployment of a quorum-based data replication scheme requires a representation of the quorum system in terms of an encoding to be stored on each process in the system.
Christian Storm

4. Analytical Evaluation of Heterogeneous Dynamic Data Replication Schemes

Abstract
The choice of a data replication scheme – and thus a particular quality measure trade-off – needs to be carefully drawn and evaluated as it is crucial to the resulting quality of the distributed system. Evaluation methods based on simulation are no good candidates because of their massive time complexity or, if run in an acceptable amount of time, their approximate nature of results. Contrarily, methods based on stochastic analysis are fast and accurate but demand for a carefully chosen higher level of abstraction in the system model: An analytical model which is as detailed as a simulation model is in general not tractable due to exponential time and space requirements. On the other hand, a higher abstraction bears the risk of oversimplification. Therefore, the analytical system model must be as precise as necessary and as abstract as possible for it to provide meaningful results and to be tractable at all.
Christian Storm

5. Example Evaluation

Abstract
In this chapter, an example evaluation of three dynamic data replication schemes performed with the system model framework introduced in the previous chapter is presented. These three data replication schemes are (1) homogeneous Dynamic Voting, (2) the homogeneous Dynamic Grid Protocol, and (3) a combination of both in terms of a heterogeneous dynamic data replication scheme, called Heterogeneous Protocol.
Christian Storm

6. Conclusion

Abstract
Quorum-based data replication is a well-established concept to improve operation availability on critical data objects in distributed systems whose components are (naturally) imperfect and subject to failures. Therefore, it is an important base concept to construct dependable distributed systems. In recent years, distributed systems have evolved from traditional statically deployed and fixed-sized systems to dynamic distributed systems. Their topology – in terms of the number of processes and their interconnecting communication infrastructure – cannot be immutably predetermined at design-time but instead is flexible and fluctuating with processes joining and deliberately departing from the system at run-time. The advent of such dynamic distributed systems demands for new means to cope with the emerging challenges posed by the dynamics. These challenges are a system’s ability to dynamically adapt to changing topologies – and possibly also to changing application requirements – and this adaptation to be performed in a best-possible manner with respect to the quality measure trade-off the system is specified for and supposed to implement.
Christian Storm

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise