Introducing Permuted States for Analyzing Conflict Rates in Optimistic Replication

摘要

We have described methods to represent and automate permuted states, which have enabled us to use analytical methods to explore the 4-replica base case of identical conflicts, and automate the analytical investigation up to 10 replicas. All results have been confirmed by an independent simulation based on version vectors. The analysis of problems with exponential state spaces is always challenging. Permuted states are a new technique that makes the analysis of complex replicated systems tractable. As a result, we can characterize and quantify important system behaviors that have previously been unrecognized or poorly understood.