Active replication of multithreaded applications

Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve performance; however, thread scheduling is a source of nondeterminism in replica behavior. To achieve strong replica consistency in multithreaded environments, this paper proposes intercepting mutex lock/unlock operations performed by threads on accessing the shared data and contributes with two algorithmic solutions: 1) a loose synchronization algorithm (LSA), which captures the natural concurrency in a leader replica and projects it on follower replicas through interreplica communication, and 2) a preemptive deterministic scheduler (PDS) algorithm, which removes the need for interreplica communication through the notion of round and by suspending threads when it is unable (yet) to schedule them deterministically. Failure behavior and performance of LSA and PDS implementations are evaluated in a triplicated system and compared with existing solutions. A performance evaluation indicates that LSA and PDS outperform existing solutions, with PDS offering lower throughput than LSA. A fault-injection campaign shows that PDS is more robust to errors due to the absence of interreplica communication. Hence, LSA and PDS represent a trade-off between performance and dependability. Finally, LSA and PDS are demonstrated in replicating the Apache Web server, a substantial real-world application.     

Microscreen-based replication of electroforming micromolds

 Novel technology is presented which allows the rapid replication of electroforming plastic micromolds. This technique incorporates microscreens into hot embossing or injection molding processes to produce sacrificial molds with conducting bases and insulating sidewalls. Both contiguous and non-contiguous features can be electroformed from these molds. Process parameters including the microscreen geometry and the use of multiple porous metal inserts are discussed. Received: 10 August 2001/Accepted: 24 September 2001     

Dynamic replication of web contents

The phenomenal growth of the World Wide Web has brought huge increase in the traffic to the popular web sites. Long delays and denial of service experienced by the end-users, especially during the peak hours, continues to be the common problem while accessing popular sites. Replicating some of the objects at multiple sites in a distributed web-server environment is one of the possible solutions to improve the response time/latency. The decision of what and where to replicate requires solving a constraint optimization problem, which is NP-complete in general. In this paper, we consider the problem of placing copies of objects in a distributed web server system to minimize the cost of serving read and write requests when the web servers have limited storage capacity. We formulate the problem as a 0-1 optimization problem and present a polynomial time greedy algorithm with backtracking to dynamically replicate objects at the appropriate sites to minimize a cost function. To reduce the solution search space, we present necessary conditions for a site to have a replica of an object in order to minimize the cost function. We present simulation results for a variety of problems to illustrate the accuracy and efficiency of the proposed algorithms and compare them with those of some well-known algorithms. The simulation results demonstrate the superiority of the proposed algorithms.     

Modeling and analysis of DNA replication

DNA replication is an important process in the life of a cell. It has to be completed with extreme accuracy in a specific phase of the cell cycle, known as the S phase. Eukaryotic DNA replication is a rather complex and uncertain process. Several mathematical models have been recently proposed in the literature to interpret experimental data from various organisms. A common concern of many of these models is the so-called random gap problem, the observation that eukaryotic DNA replication should last longer than experimental evidence suggests due to its stochastic nature. One of the biological hypotheses proposed for resolving the random gap problem postulates the presence of a limiting factor regulating the rate with which DNA replication initiates. We show how this hypothesis can be captured in the Piecewise Deterministic Markov Process modeling framework. Monte Carlo simulations allow us to analyze the proposed model and compare model predictions with independent experimental data.     

On speculative replication of transactional systems

In this paper we investigate, from a theoretical perspective, the problem of how to build speculative replication protocols for transactional systems layered on top of an Optimistic Atomic Broadcast (OAB) service. The OAB service provides an early, possibly erroneous, guess on transactionʼs final serialization order. This can be exploited to speculatively execute transactions in parallel with the algorithm used to determine their final total delivery (and serialization) order. To maximize the chances of guessing their final serialization order, transactions are executed multiple times, speculating on the possible orderings eventually determined by the OAB service. We formalize the Speculative Transactional Replication (STR) problem by means of a set of properties ensuring that transactions are never activated on inconsistent snapshots, as well as the minimality and completeness of the set of speculatively explored serialization orders. Finally, we present a protocol solving the STR problem, along with simulation results assessing its effectiveness.     

X-Ability: a theory of replication

Summary.   Different replication algorithms provide different solutions to the same basic problem. However, there is no precise specification of the problem itself, only of particular classes of solutions, such as active replication and primary-backup. Having a precise specification of the problem would help us better understand the space of possible solutions and possibly come out with new ones. We present a formal definition of the problem solved by replication in the form of a correctness criterion called x-ability (exactly-once ability). An x-able service has obligations to its environment and its clients. It must update its environment under exactly-once semantics. Furthermore, it must provide idempotent, non-blocking request processing and deliver consistent results to its clients. We illustrate the value of x-ability through a novel replication protocol that handles non-determinism and external side-effects. The replication protocol is asynchronous in the sense that it may vary, at run-time and according to the asynchrony of the system, between some form of primary-backup and some form of active replication. Received: December 2000 / Accepted: September 2001     

Computational methods for option replication

A computational method is described for option replication. In particular, a procedure is provided for computing the projection basis that corresponds to a positive basis of ? ^m . Application of this procedure in order to compute maximal submarkets that replicate any option is demonstrated. Specifically, we provide a computational study for the replication of options in security markets with a finite number of states and a finite number of primitive assets with payoffs given by linearly independent vectors of ? ^m . The theoretical background of this work follows the results in Polyrakis and Xanthos [Maximal submarkets that replicate any option, Ann. Finance, DOI: 10.1007/s10436-009-0143-9]. Our goal is to make option replication computationally tractable and hence more viable as a financial tool.     

A real-time primary-backup replication service

This paper presents a real-time primary-backup replication scheme to support fault-tolerant data access in a real-time environment. The main features of the system are fast response to client requests, bounded inconsistency between primary and backup, temporal consistency guarantee for replicated data, and quick recovery from failures. The paper defines external and interobject temporal consistency, the notion of phase variance, and builds a computation model that ensures such consistencies for replicated data deterministically where the underlying communication mechanism provides deterministic message delivery semantics and probabilistically where no such support is available. It also presents an optimization of the system and an analysis of the failover process which includes failover consistency and failure recovery time. An implementation of the proposed scheme is built within the x-kernel architecture on the MK 7.2 microkernel from the Open Group. The results of a detailed performance evaluation of this implementation are also discussed     

Semi-passive replication and Lazy Consensus

This paper presents two main contributions: semi-passive replication and Lazy Consensus. The former is a replication technique with parsimonious processing. It is based on the latter; a variant of Consensus allowing the lazy evaluation of proposed values.Semi-passive replication is a replication technique with parsimonious processing. This means that, in the normal case, each request is processed by only one single process. The most significant aspect of semi-passive replication is that it requires a weaker system model than existing techniques of the same family. For semi-passive replication, we give an algorithm based on the Lazy Consensus.Lazy Consensus is a variant of the Consensus problem that allows the lazy evaluation of proposed values, hence the name. The main difference with Consensus is the introduction of an additional property of laziness. This property requires that proposed values are computed only when they are actually needed. We present an algorithm based on Chandra and Toueg's Consensus algorithm for asynchronous distributed systems with a S failure detector.     

Implementing E-transactions with asynchronous replication

This paper describes a distributed algorithm that implements the abstraction of e-Transaction: a transaction that executes exactly-once despite failures. Our algorithm is based on an asynchronous replication scheme that generalizes well-known active-replication and primary-backup schemes. We devised the algorithm with a three-tier architecture in mind: the end-user interacts with front-end clients (e.g., browsers) that invoke middle-tier application servers (e.g., web servers) to access back-end databases. The algorithm preserves the three-tier nature of the architecture and introduces a very acceptable overhead with respect to unreliable solutions     

Software-based replication for fault tolerance

Replication handled by software on off-the-shelf hardware costs less than using specialized hardware. Although an intuitive concept, replication requires sophisticated techniques for successful implementation. Group communication provides an adequate framework. We present a survey of the techniques developed since the mid-1980s to implement replicated services, emphasizing the relationship between replication techniques and group communication     

高性能的异步复制系统的设计

为了提高整个远程复制系统的性能,对卷复制系统进行了优化.采用了多线程并行处理技术和流水线技术,设计了一种高性能的日志和位图,采用了网络自适应的复制协议和高效的请求合并策略.实验结果表明,该优化策略减少了应用等待的时间,降低了网络发送的时间开销,合理利用了有限的复制带宽,提高了复制效率.     

Analysis of replication in distributed database systems

The authors develop an approximate analytical model to study the tradeoffs of replicating data in a distributed database environment. Several concurrency control protocols are considered, including pessimistic, optimistic, and semi-optimistic protocols. The approximate analysis captures the effect of the protocol on hardware resource contention and data contention. The accuracy of the approximation is validated through detailed simulations. It is found that the benefit of replicating data and the optimal number of replicates are sensitive to the concurrency control protocol. Under the optimistic and semi-optimistic protocols, replications can significantly improve response time with an additional MIPS (million instructions per second) requirement to maintain consistency among the replicates. The optimal degree of replication is further affected by the transaction mix (e.g. the fraction of read-only transactions), the communications delay and overhead, the number of distributed sites, and the available MIPS. Sensitivity analyses have been carried out to examine how the optimal degree of replication changes with respect to these factors     

A threshold-based dynamic data replication strategy

Data replication is the creation and maintenance of multiple copies of the same data. Replication is used in Data Grid to enhance data availability and fault tolerance. One of the main objectives of replication strategies is reducing response time and bandwidth consumption. In this paper, a dynamic replication strategy that is based on Fast Spread but superior to it in terms of total response time and total bandwidth consumption is proposed. This is achieved by storing only the important replicas on the storage of the node. The main idea of this strategy is using a threshold to determine if the requested replica needs to be copied to the node. The simulation results show that the proposed strategy achieved better performance compared with Fast Spread with Least Recently Used (LRU), and Fast Spread with Least Frequently Used (LFU).     

Optimal stream replication for video simulcasting

Video simulcasting enables a sender to generate replicated streams of different rates, serving receivers of diverse access bandwidths. As replication introduces noticeable redundancy, balancing bandwidth consumption with user satisfaction becomes a critical concern in simulcasting. This paper investigates the above issue; more explicitly, we seek answers to the following two questions: what is the number of streams that should be generated, and what is the bandwidth that should be allocated to each stream? We derive optimal and efficient solutions, and evaluate their performance under a variety of configurations. The results demonstrate that an optimal and adaptive bandwidth allocation significantly improves user satisfaction under stringent resource constraints, and an optimal choice of the stream number yields further improvements.     

Selective replication for content management environments

Content management applications typically depend on information stored in both relational database tables and operating system files. Often, content providers replicate all or parts of the available database data and associated files to increase application availability, address resource constraints and costs, or better support geographically dispersed and mobile users. This article presents a solution that addresses integrated and selective database and file replication in the context of an enterprise voice portal. The solution is transparent to existing applications and imposes minimal storage overhead.     

Fully distributed three-tier active software replication

Keeping strongly consistent the state of the replicas of a software service deployed across a distributed system prone to crashes and with highly unstable message transfer delays (e.g., the Internet), is a real practical challenge. The solution to this problem is subject to the FLP impossibility result, and thus there is a need for "long enough" periods of synchrony with time bounds on process speeds and message transfer delays to ensure deterministic termination of any run of agreement protocols executed by replicas. This behavior can be abstracted by a partially synchronous computational model. In this setting, before reaching a period of synchrony, the underlying network can arbitrarily delay messages and these delays can be perceived as false failures by some timeout-based failure detection mechanism leading to unexpected service unavailability. This paper proposes a fully distributed solution for active software replication based on a three-tier software architecture well-suited to such a difficult setting. The formal correctness of the solution is proved by assuming the middle-tier runs in a partially synchronous distributed system. This architecture separates the ordering of the requests coming from clients, executed by the middle-tier, from their actual execution, done by replicas, i.e., the end-tier. In this way, clients can show up in any part of the distributed system and replica placement is simplified, since only the middle-tier has to be deployed on a well-behaving part of the distributed system that frequently respects synchrony bounds. This deployment permits a rapid timeout tuning reducing thus unexpected service unavailability.     

Service replication taxonomy in distributed environments

Abstract Nowadays, most modern distributed environments, including service-oriented architecture (SOA), cloud computing, and mobile computing, support replication technologies in order to improve operational characteristics of the services provided. Unfortunately, replication requires additional computational resources and a longer design and deployment process to implement service adequately for a specific situation and to enable service providers to maintain high levels of service with a moderate number of replicas. This paper provides a comprehensive review of replication challenges, types, techniques, and algorithms in distributed environments such as SOA, cloud, and mobile. Moreover, the role of replication in enhancing several QoS attributes, including performance, availability, security, scalability, and reliability, is examined. The author believes that the proposed research will help researchers to easily apply and develop the service replication in distributed system.