RPECA-Rumor Propagation Based Eventual Consistency Assessment Algorithm

详细信息    查看全文

• 关键词：Eventually consistency ; Rumor propagation ; Markov chain ; Across ; datacenter
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9231
• 期：1
• 页码：60-72
• 全文大小：2,404 KB
• 参考文献：1.Gilbert, S., Lynch, N.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. In: ACM SIGACT News, vol. 33, pp. 51-9 (2002)
  2.Abadi, D.J.: Consistency tradeoffs in modern distributed database system design: CAP is only part of the story. Computer 2, 37-2 (2012)View Article
  3.Wen, D., Wang, H.-M., Yan, J., Peng, Z.: A rumor-spreading analog on unstructured P2P broadcast mechanism. J. Comput. Res. Dev. 41, 1460-465 (2004)
  4.Birman, K.: Reliable Distributed Systems Technologies, Web Services and Applications. Springer Science and Business Media, New York (2005)MATH
  5.Bailis, P., Venkataraman, S., Franklin, M., Hellerstein, J., Stoica, I.: Probabilistically bounded staleness for practical partial quorums. In: Proceedings of the VLDB Endowment, pp. 776-87 (2012)
  6.Zellag, K., Kemme, B.: How consistent is your cloud application? In: Proceedings of the Third ACM Symposium on Cloud Computing (2012)
  7.Bermbach, D., Kuhlenkamp, J.: Consistency in distributed storage systems: an overview of models, metrics and measurement approaches. In: Proceedings of the International Conference on Networked Systems (NETYS), vol. 7853, pp.175-89. Springer, Heidelberg (2013)
  8.Rahman, M., Golab, W., AuYoung, A., Keeton, K., Wylie, J.: Toward a principled framework for benchmarking consistency. In: Proceedings of the Eighth USENIX Conference on Hot Topics in System Dependability, p. 8. USENIX Association (2012)
  9.Golab, W., Li, X., Shah, M.A.: Analyzing consistency properties for fun and profit. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 197-06. ACM press (2011)
  10.Erdos, P., Renyi, A.G.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. A247, 529-51 (1955)
  11.Watts, D.J., Strongatz, S.H.: Collective dynamics of ‘small-world-networks. Nature 393, 440-42 (1998)View Article
  12.Newman, M.E.J., Watts, D.J.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341-46 (1999)MATH MathSciNet View Article
  13.Barabasi, A.L., Albert, R.: Emergence of scalling in random networks. Science 286, 509-12 (1999)MathSciNet View Article
  14.Satorrasr, R.P., Vespignani, A.: Evolution and Structure of the Internet: a Statistical Physics Approach. Cambridge University Press, Cambridge (2004)View Article
  15.Caldarelli, G.: ScaSle-Free Networks. Oxford University Press, Oxford (2007)View Article
  16.Zanette, D.H.: Dynamics of rumor propagation on small-world networks. Phys. Rev. E. 64, 041908 (2002)View Article
  17.Moreno, Y., Nekovee, M., Pacheco, A.F.: Dynamics of rumor spreading in complex networks. Phys. Rev. E. 69, 066130 (2004)View Article
  18.Dodds, P.S., Watts, D.J.: Universal behavior in a generalized model of contagion. Phys. Rev. Lett. 92, 218701 (2004)View Article
  19.Moreno, Y., Gomez, J.B., Pacheco, A.F.: Epidemic incidence in correlated complex networks. Phys. Rev. E 68, 035103 (2003)View Article
  20.Zanette, D.H.: Critical behavior of propagation on small-world networks. Phys. Rev. E 64, 050901 (2001)View Article
  21.Anderson, R.M., May, R.M.: Infections Disease of Humans. Oxford University Press, Oxford (1991)
  22.Gomez, S., Arenas, A.: Discrete-time Markov chain approach to contact-based disease spreading in complex networks. Europhys. Lett. 89, 38009 (2010)View Article
  23.Gomez, S., Arenas, A.: Probabilistic framework for epidemic spreading in complex networks. Int. J. Complex Syst. Sci. 1, 47-4 (2011)
  24.Nekovee, M., Moreno, Y., Bianconi, G., Marsili, M.: Theory of rumor spreading in complex social networks. Physica A 374, 457-70 (2007)View Article
  25.Maki, D.P.: Mathematical Models and Applications, with Emphasis on Social, Life, and Management Sciences. Prentice-Hall, Englewood Cliffs (1973)
  26.Daley, D.J., Gani, J.: Epidemic Modelling. Cambridge University Press, Cambridge (2000)
  27.Newman, M.E.J., Watts, D.J.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341-46 (1999)MATH MathSciNet View Article
  
• 作者单位：Dong Zhang (16) (17)
  Zhiyuan Su (16) (17)
  Kaiyuan Qi (16) (17)
  Guomao Xin (16) (17)
  Peng Wei (16) (17)
  
  16. State Key Laboratory of High-End Server and Storage Technology, Jinan, 250101, China
  17. Inspur Electronic Information Industry Co., Ltd., Jinan, 250101, China
  
• 丛书名：Advanced Parallel Processing Technologies
• ISBN：978-3-319-23216-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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.