Use of Genetic Programming Operators in Data Replication and Fault Tolerance

Distributed systems are a need of the current times to balance the workload since providing highly accessible data objects is of utmost importance. Faults hinder the availability of the data, thereby leading systems to fail. In this regard, data replication in distributed systems is a means to mask failures and mitigate any such possible hindrances in the availability of the data. This replicated behavior is then controlled by data replication strategies, but there are numerous scenarios reflecting different trade-offs between several quality metrics. It demands designing new replication strategies optimized for the given scenarios, which may be left unaddressed otherwise. This research, therefore, uses an automatic mechanism based on genetic programming to construct new optimized replication strategies (up-to-now) unknown. This mechanism uses a so-called voting structure of directed acyclic graphs (each representing a computer program) as a unified representation of replication strategies. These structures are interpreted by our general algorithm at run-time in order to derive respective quorums to manage replicated objects eventually. For this, the research particularly demonstrates the usefulness of various genetic operators through their instances, exploiting the heterogeneity between existing strategies, thereby creating innovative strategies flexibly. This mechanism creates new hybrid strategies and evolves them over several generations of evolution, to make them optimized while maintaining the consistency (validity) of the solutions. Our approach is very effective and extremely flexible to offer competitive results with respect to the contemporary strategies as well as generating novel strategies even with a slight use of relevant genetic operators.

I. Introduction

Providing highly available data access operations is a common challenge in computer sciences. The data access operations are to read or write the data. If a system depends only on a single replica, it greatly limits the availability of the data. Thus, an increasing number of replicas to save the data objects becomes necessary, which as a result improves the availability of the data. This makes the system more fault-tolerant since data can be accessed by other replicas, as well. However, now the challenge comes up in managing those replicas to eliminate the consistency as well as concurrency problems. For instance, if there are multiple replicas of the same data object and one of them is updated with a new value and a user accesses the value from another replica (that stills keeps the old value), this is an incorrect value. This is not the intended behavior of the system, which is known as the consistency problem. In addition, the data must be exclusively locked for the write operation to again adhere to the correctness notion. These problems indicate that creating several replicas with simply the aim of achieving high availability does not yield the expected outcome at all.