Modeling and Simulation of Optimistic Replication

An-I Andy Wang , Florida State University
Geoffrey H. Kuenning, Harvey Mudd College
Peter Reiher and Rajive Bagrodia, University of California, Los Angeles

Optimistic peer replication provides high data availability in the presence of network outages. Although widely deployed, this relaxed consistency model introduces concurrent updates, which the behavior is poorly understood due to the vast state space.

We have pioneered the notion of permuted states to eliminate system states that are redundant and unreachable, which constitute 99% of the state space for as few as six replicas. With the aid of the permuted states, we are for the first time able to construct analytical models beyond the two-replica case. By walking through the analysis for 2 to 4 replicas, we can demystify the process of forming identical conflicts-the most common conflict type at high replication factors. Additionally, we have automated and optimized the generation of permuted states, which allows us to explore higher replication factors. It also allows us to validate our results with simulations that are based on the actual replication mechanisms, which are typically validated with only one pair of replicas.

Our developed simulation can support a large-scale, heterogeneous, distributed environment specified by its own input language. The abstraction of library components allows the extension of our simulator to match a variety of system settings. The input traffic emulates actual trace data collected at a representative office-computing environment. The simulator is developed using Maisie, a C-based discrete-event simulation language, which enables parallel execution of the simulation.

Our simulation revealed that the widely used conflict rate metric is misleading: If you never exchange updates, you will never have a conflict. We investigated this anomaly and proposed alternative metrics to evaluate the service quality of optimistic replication. In addition, the deduced operational costs from simulation suggest that we can economically achieve a high quality of optimistic replication service. We demonstrated also that optimistic replication scales well, and the low percentage of active users in a large distributed system self-regulates service quality. Finally, we have discovered that update locality and bimodal access patterns are the primary factors contributing to the formation of identical conflicts.

Publications

Wang07
An-I Andy Wang, Geoff Kuenning, and Peter Reiher. Using Permuted States and Validated Simulation to Analyze Conflict Rates in Optimistic Replication. SCS Simulation: Transactions of the Society for Modeling and Simulation International, 83(8), pp. 551-569, August 2007.

Wang05b
An-I Andy Wang, Geoffrey H. Kuenning, Peter Reiher. Using Permuted States and Validated Simulation to Analyze Conflict Rates in Optimistic Replication, 2005 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), July 2005.<http://www.cs.fsu.edu/~awang/papers/spects2005.html>

Wang05a
An-I Andy Wang, Geoffrey H. Kuenning, Peter Reiher. Introducing Permuted States for Analyzing Conflict Rates in Optimistic Replication, ACM International Conference on Measurement & Modeling of Computer Systems (SIGMETRICS), June 2005.

Wang02c
An-I Andy Wang, Peter Reiher, Rajive Bagrodia, Geoffrey H. Kuenning. Understanding the Behavior of the Conflict-Rate Metric in Optimistic Peer Replication. Proceedings of the 5th IEEE International Workshop on Mobility in Databases and Distributed Systems (MDDS), Aix-en-Provence, France, September 2002. <http://www.cs.fsu.edu/~awang/papers/mdds2002a.html>

Wang01b
An-I Andy Wang, Peter Reiher, Rajive Bagrodia. A Simulation Framework and Evaluation for Optimistically Replicated Filing Environments. Technical report CSD-010046, Computer Science Department, University of California, Los Angeles, 2001. <http://www.cs.fsu.edu/~awang/papers/ucla2001a.html>

Wang99b
An-I Andy Wang, Peter Reiher, Rajive Bagrodia. Validation Experiences of the Simulation Framework for Optimistically Replicated Filing Environments: A Case Study. Proceedings of the DARPA/NIST Network Simulation Validation Workshop, Fairfax, Virginia, May 1999.

Wang99a
An-I Andy Wang, Peter Reiher, Rajive Bagrodia. A Simulation Evaluation of Optimistically Replicated Filing in Mobile Environments. Proceedings of the 18th IEEE International Performance, Computing, and Communication Conference (IPCCC), Phoenix/Scottsdale, Arizona, February 1999. <http://www.cs.fsu.edu/~awang/papers/ipccc1999a.html>

Kuenning98
Geoffrey H. Kuenning, Richard G. Guy, Gerald J. Popek, Peter Reiher, An-I Andy Wang. Measuring the Quality of Service of Optimistic Replication. Proceedings of the 12th European Conference on Object-Oriented Programming (ECOOP) Workshop on Mobility and Replication, Brussels, Belgium, July 1998. <http://www.cs.fsu.edu/~awang/papers/ecoop1998a.html>

Wang98
An-I Andy Wang. A Simulation Evaluation for Optimistically Replicated Filing Environments. Master's Thesis. Computer Science Department, University of California, Los Angeles, 1998.

Wang97
An-I Andy Wang, Peter Reiher, Rajive Bagrodia. A Simulation Framework for Evaluating Optimistically Replicated Filing Environments. Technical report CSD-970018. Computer Science Department, University of California, Los Angeles, 1997.
awang@cs.fsu.edu

Last modified:  Feb 1, 2005