Abstract
Managing replicated data in distributed systems that is concurrently accessed by multiple sites is a complex task, because consistency must be ensured. In this paper, we present the Replicated Convergent Data Containers (RCDCs) - a set of distributed data structures that coordinate replicated data and allow for optimistic inserts, updates and deletes in a lock-free, non-blocking fashion. It is crucial that continuous data harmonization among containers takes place over time. This is achieved by a synchronization mechanism that is based on a technique called Operational Transformation (OT) which continously reconciles diverging containers. A generic architecture is placed on top of this underlying synchronization mechanism that allows to realize a multitude of different RCDCs. Two container specializations are presented: (a) the linear container that organizes data in an ordered sequence, (b) the hierarchical container that organizes the data in an n-ary tree.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
The collections framework @MISC, http://docs.oracle.com/javase/7/docs/technotes/guides/collections/
Granite data services @MISC, https://www.granitedataservices.com/
Ellis, C.A., Gibbs, S.J.: Concurrency control in groupware systems. SIGMOD Rec. 18(2), 399–407 (1989), http://doi.acm.org/10.1145/66926.66963
Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns: Elements of Reusable Object-oriented Software. Addison-Wesley Longman Publishing Co., Inc., Boston (1995)
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978), http://doi.acm.org/10.1145/359545.359563
Letia, M., Preguiça, N., Shapiro, M.: Consistency without concurrency control in large, dynamic systems. SIGOPS Oper. Syst. Rev. 44(2), 29–34 (2010), http://doi.acm.org/10.1145/1773912.1773921
Liskov, B., Zilles, S.: Programming with abstract data types. In: Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages, pp. 50–59. ACM, New York (1974), http://doi.acm.org/10.1145/800233.807045
Mattern, F.: Virtual time and global states of distributed systems. In: Parallel and Distributed Algorithms, pp. 215–226. North-Holland (1988)
Nichols, D.A., Curtis, P., Dixon, M., Lamping, J.: High-latency, low-bandwidth windowing in the jupiter collaboration system. In: Proceedings of the 8th Annual ACM Symposium on User Interface and Software Technology, UIST 1995, pp. 111–120. ACM, New York (1995), http://doi.acm.org/10.1145/215585.215706
Roh, H.G., Jeon, M., Kim, J.S., Lee, J.: Replicated abstract data types: Building blocks for collaborative applications. J. Parallel Distrib. Comput. 71(3), 354–368 (2011), http://dx.doi.org/10.1016/j.jpdc.2010.12.006
Saito, Y., Shapiro, M.: Optimistic replication. ACM Comput. Surv. 37(1), 42–81 (2005), http://doi.acm.org/10.1145/1057977.1057980
Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types. In: Défago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 386–400. Springer, Heidelberg (2011)
Sun, C., Ellis, C.: Operational transformation in real-time group editors: Issues, algorithms, and achievements. In: Proceedings of the 1998 ACM Conference on Computer Supported Cooperative Work, CSCW 1998, pp. 59–68. ACM, New York (1998), http://doi.acm.org/10.1145/289444.289469
Wang, D., Mah, A., Lassen, S.: Google wave operational transformation type @MISC (2010), http://wave-protocol.googlecode.com/hg/whitepapers/operational-transform/operational-transform.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Herb, T., Kao, O. (2014). Replicated Convergent Data Containers. In: Ait Ameur, Y., Bellatreche, L., Papadopoulos, G.A. (eds) Model and Data Engineering. MEDI 2014. Lecture Notes in Computer Science, vol 8748. Springer, Cham. https://doi.org/10.1007/978-3-319-11587-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-11587-0_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11586-3
Online ISBN: 978-3-319-11587-0
eBook Packages: Computer ScienceComputer Science (R0)