RPECA-Rumor Propagation Based Eventual Consistency Assessment Algorithm

摘要

Replicating data across servers or storages in different data centers allows using data closer to the client and reducing latency for applications, In addition, it also increases the availability in the event of one or some datacenters failure. Hence, replica consistency among all nodes is a major consideration when designing high-availability across-domain datacenters. Even lots of mechanisms are proposed to reach this consistency target, we believe knowing the degree of consistency is helpful to an application developer as the dimension of uncertainty is reduced: The quality of service (QoS) becomes, to some degree, predictable. For this purpose, this paper proposes a novel algorithm called RPECA which can be applied to monitor consistency behaviors in a cost-efficient way. RPECA is based on theory of rumor propagation in complex networks. In this paper, we focus on the probability of each node's specific status in the network (Ignorant, Spreader or Stifler). Based on the discrete-time markov chain model technique, we apply a set of topology-independent equations to describe the microscope dynamic property of each node at any given time. Besides, we construct the whole phase diagram of the rumor spreading process in SF and small-world networks to simulate consistency behavior. In the experimental part, on one hand, the numerical results of our RPECA method could almost coincide with the empirical results of Monte Carlo (MC) simulations, which proves that our algorithm could simulated the whole phase diagram correctly. On the other hand, since the numerical results could be solved with less iterations, our RPECA algorithm could significantly outperform MC method with respect to time complexity.