Optimistic Scheduling with Geographically Replicated Services in the Cloud Environment (COLOR)

This paper proposes a system model that unifies different optimistic algorithms designed for deploying geographically replicated services in a cloud environment. The proposed model thereby enables a generalized solution (COLOR) by which well-specified safety and timeliness guarantees are achievable in conjunction with tunable performance requirements. The proposed solution explicitly takes advantage of the unique client-cloud interface in specifying how the level of consistency violation may be bounded, for instance using probabilistic rollbacks or restarts as parameters. The solution differs from traditional Eventual Consistency models in that inconsistency is solved concurrently with online client-cloud interactions over strongly connected networks. We believe that such an approach will bring clarity to the role and limitations of the ever-popular Eventual Consistency model in cloud services.