This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Wang, A.-I A. Articles by Reiher, P. Search for Related Content Social Bookmarking                         What's this?

Using Permuted States and Validated Simulation to Analyze Conflict Rates in Optimistic Replication

Computer Science Department Florida State University, Tallahassee, FL, USA awang{at}cs.fsu.edu

Geoff Kuenning

Computer Science Department Harvey Mudd College, Claremont, CA, USA

Peter Reiher

Computer Science Department University of California, Los Angeles, CA, USA

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

This paper introduces the notion of permuted states to eliminate system states that are redundant and unreachable, which can constitute the majority of states (4069 out of 4096 for four replicas). With the aid of permuted states, we are for the first time able to construct analytical models beyond the two-replica case. By eXamining 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 (up to 10 replicas) using hybrid techniques. It also allows us to validate our results with eXisting simulations based on actual replication mechanisms, which previously were analytically validated with only one pair of replicas.

Finally, we have discovered that update locality and bimodal access patterns are the primary factors contributing to the formation of identical conflicts.

Key Words: permuted states • optimistic replication • conflict rates

SIMULATION, Vol. 83, No. 8, 551-569 (2007)
DOI: 10.1177/0037549707085073


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?