Abstract
Coordination languages for tuple spaces can offer significant advantages in the specification and implementation of distributed systems, but often do require manual programming effort to ensure consistency. We propose an experimental technique for automated replication of tuple spaces in distributed systems. The system of interest is modelled as a concurrent Go program where different threads represent the behaviour of the separate components, each owning its own local tuple repository. We automatically transform the initial program by combining program transformation and static analysis, so that tuples are replicated depending on the components’ read-write access patterns. In this way, we turn the initial system into a replicated one where the replication of tuples is automatically achieved, while avoiding unnecessary replication overhead. Custom static analyses may be plugged in easily in our prototype implementation. We see this as a first step towards developing a fully-fledged framework to support designers to quickly evaluate many classes of replication-based systems under different consistency levels.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andrić, M., De Nicola, R., Lafuente, A.L.: Replica-based high-performance tuple space computing. In: Holvoet, T., Viroli, M. (eds.) COORDINATION 2015. LNCS, vol. 9037, pp. 3–18. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19282-6_1
Andrić, M., De Nicola, R., Lluch Lafuente, A.: Replicating data for better performances in X10. In: Probst, C.W., Hankin, C., Hansen, R.R. (eds.) Semantics, Logics, and Calculi. LNCS, vol. 9560, pp. 236–251. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-27810-0_12
Bessani, A.N., Alchieri, E.A.P., Correia, M., da Silva Fraga, J.: DepSpace: a Byzantine fault-tolerant coordination service. In: EuroSys, pp. 163–176. ACM (2008)
Bettini, L., De Nicola, R., Pugliese, R.: KLAVA: a Java package for distributed and mobile applications. Softw. Pract. Exp. 32(14), 1365–1394 (2002)
Casadei, M., Viroli, M., Gardelli, L.: On the collective sort problem for distributed tuple spaces. Sci. Comput. Program. 74(9), 702–722 (2009)
Corradi, A., Leonardi, L., Zambonelli, F.: Distributed tuple spaces in highly parallel systems. Technical report, DEISLIA-96-005, UNIBO (Italy) (1996)
Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: POPL, pp. 84–96. ACM Press (1978)
De Nicola, R., Ferrari, G.L., Pugliese, R.: KLAIM: a kernel language for agents interaction and mobility. IEEE Trans. Softw. Eng. 24(5), 315–330 (1998)
De Nicola, R., et al.: The SCEL language: design, implementation, verification. In: Wirsing, M., Hölzl, M., Koch, N., Mayer, P. (eds.) Software Engineering for Collective Autonomic Systems. LNCS, vol. 8998, pp. 3–71. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16310-9_1
De Nicola, R., Pugliese, R., Rowstron, A.: Proving the correctness of optimising destructive and non-destructive reads over tuple spaces. In: Porto, A., Roman, G.-C. (eds.) COORDINATION 2000. LNCS, vol. 1906, pp. 66–80. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45263-X_5
Elnikety, S., Dropsho, S.G., Zwaenepoel, W.: Tashkent+: memory-aware load balancing and update filtering in replicated databases. In: EuroSys, pp. 399–412. ACM (2007)
Fekete, A.D., Ramamritham, K.: Consistency models for replicated data. In: Charron-Bost, B., Pedone, F., Schiper, A. (eds.) Replication. LNCS, vol. 5959, pp. 1–17. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11294-2_1
Gelernter, D.: Generative communication in Linda. ACM (TOPLAS) 7(1), 80–112 (1985)
Kaki, G., Earanky, K., Sivaramakrishnan, K.C., Jagannathan, S.: Safe replication through bounded concurrency verification. Proc. ACM Program. Lang. 2(OOPSLA), 164:1–164:27 (2018)
Kaminskas, L., Lluch, L.A.: Aggregation policies for tuple spaces. In: Di Marzo Serugendo, G., Loreti, M. (eds.) COORDINATION 2018. LNCS, vol. 10852, pp. 181–199. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92408-3_8
Karandikar, R.R., Gudadhe, M.B.: Comparative analysis of dynamic replication strategies in cloud. IJCA TACIT2016(1), 26–32 (2016)
Lange, J., Ng, N., Toninho, B., Yoshida, N.: Fencing off go: liveness and safety for channel-based programming. In: POPL, pp. 748–761. ACM (2017)
Lange, J., Ng, N., Toninho, B., Yoshida, N.: A static verification framework for message passing in Go using behavioural types. In: ICSE, pp. 1137–1148. ACM (2018)
Lattner, C.: LLVM and Clang: next generation compiler technology. In: The BSD Conference (2008)
Mamei, M., Zambonelli, F., Leonardi, L.: Tuples on the air: a middleware for context-aware multi-agent systems. In: WOA, pp. 108–116. PEB (2002)
Murphy, A.L., Picco, G.P.: Using Lime to support replication for availability in mobile ad hoc networks. In: Ciancarini, P., Wiklicky, H. (eds.) COORDINATION 2006. LNCS, vol. 4038, pp. 194–211. Springer, Heidelberg (2006). https://doi.org/10.1007/11767954_13
Pike, R.: Go at Google. In: SPLASH, pp. 5–6. ACM (2012)
Quinlan, D., Liao, C.: The ROSE source-to-source compiler infrastructure. In: Cetus Users and Compiler Infrastructure Workshop, in conj. with PACT (2011)
Russello, G., Chaudron, M., van Steen, M.: Dynamically adapting tuple replication for managing availability in a shared data space. In: Jacquet, J.-M., Picco, G.P. (eds.) COORDINATION 2005. LNCS, vol. 3454, pp. 109–124. Springer, Heidelberg (2005). https://doi.org/10.1007/11417019_8
Saraswat, V., Jagadeesan, R.: Concurrent clustered programming. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 353–367. Springer, Heidelberg (2005). https://doi.org/10.1007/11539452_28
Stoica, I., Morris, R.T., Karger, D.R., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. In: SIGCOMM, pp. 149–160. ACM (2001)
Terry, D.: Replicated data consistency explained through baseball. Commun. ACM 56(12), 82–89 (2013)
Wegman, M.N., Zadeck, F.K.: Constant propagation with conditional branches. ACM Trans. Program. Lang. Syst. 13(2), 181–210 (1991)
Acknowledgements
Work partially funded by MIUR project PRIN 2017FTXR7S IT MATTERS (Methods and Tools for Trustworthy Smart Systems).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 IFIP International Federation for Information Processing
About this paper
Cite this paper
Uwimbabazi, A., Inverso, O., De Nicola, R. (2021). Automated Replication of Tuple Spaces via Static Analysis. In: Hojjat, H., Massink, M. (eds) Fundamentals of Software Engineering. FSEN 2021. Lecture Notes in Computer Science(), vol 12818. Springer, Cham. https://doi.org/10.1007/978-3-030-89247-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-89247-0_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89246-3
Online ISBN: 978-3-030-89247-0
eBook Packages: Computer ScienceComputer Science (R0)
