×

Implementing set objects in dynamic distributed systems. (English) Zbl 1338.68019

Summary: This paper considers a set object, i.e., a shared object allowing users (processes) to add and remove elements to the set, as well as taking consistent snapshots of its content. Specifically, we show that there not exists any protocol implementing a set object, using finite memory, when the underlying distributed system is eventually synchronous and affected by continuous arrivals and departures of processes (phenomenon also known as churn). Then, we analyze the relationship between system model assumptions and object specification in order to design protocols implementing the set object using finite memory. Along one direction (strengthening the system model), we propose a protocol implementing the set object in synchronous distributed systems and, along the other direction (weakening the object specification), we introduce the notion of a \(k\)-bounded set object proposing a protocol working on an eventually synchronous system.

MSC:

68M14 Distributed systems
68P05 Data structures

Software:

Chord; LIME; Linda
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aguilera, M. K., A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, 35, 2, 36-59 (2004)
[2] Aguilera, M. K.; Keidar, I.; Malkhi, D.; Shraer, A., Dynamic atomic storage without consensus, J. ACM, 58, 2, 7 (2011) · Zbl 1327.68093
[3] Ahamad, M.; Neiger, G.; Burns, J. E.; Kohli, P.; Hutto, P. W., Causal memory: definitions, implementation, and programming, Distrib. Comput., 9, 1, 37-49 (1995) · Zbl 1448.68057
[4] Baldoni, R.; Bonomi, S.; Kermarrec, A. M.; Raynal, M., Implementing a register in a dynamic distributed system, (29th IEEE International Conference on Distributed Computing Systems. 29th IEEE International Conference on Distributed Computing Systems, 2009, ICDCS’09 (2008), IEEE), 639-647
[5] Baldoni, R.; Bonomi, S.; Raynal, M., Implementing a regular register in an eventually synchronous distributed system prone to continuous churn, IEEE Trans. Parallel Distrib. Syst., 23, 1, 102-109 (January 2012)
[6] Cavin, D.; Sasson, Y.; Schiper, A., Consensus with unknown participants or fundamental self-organization, (ADHOC-NOW (2004)), 135-148
[7] Delporte-Gallet, C.; Fauconnier, H., Two consensus algorithms with atomic registers and failure detector \(ω\), (Proceedings of the 10th International Conference on Distributed Computing and Networking. Proceedings of the 10th International Conference on Distributed Computing and Networking, ICDCN ’09 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 251-262
[8] Friedman, R.; Raynal, M.; Travers, C., Two abstractions for implementing atomic objects in dynamic systems, (Proceedings of the 9th International Conference on Principles of Distributed Systems. Proceedings of the 9th International Conference on Principles of Distributed Systems, OPODIS’05 (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 73-87
[9] Gelernter, D., Generative communication in Linda, ACM Trans. Program. Lang. Syst., 7, 1, 80-112 (1985) · Zbl 0559.68030
[10] Greve, F.; Tixeuil, S., Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks, (2007 IEEE/IFIP International Conference on Dependable Systems and Networks. 2007 IEEE/IFIP International Conference on Dependable Systems and Networks, DSN (2007), IEEE Computer Society)
[11] Guerraoui, R.; Levy, R. R.; Pochon, B.; Pugh, J., The collective memory of amnesic processes, ACM Trans. Algorithms, 4, 1, 12:1-12:31 (March 2008)
[12] Hadzilacos, V.; Toueg, S., Reliable broadcast and related problems, (Distributed Systems (1993)), 97-145
[13] Herlihy, M. P.; Wing, J. M., Linearizability: a correctness condition for concurrent objects, ACM Trans. Program. Lang. Syst., 12, 3, 463-492 (1990)
[14] Ko, S. Y.; Hoque, I.; Gupta, I., Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols, (IEEE Symposium on Reliable Distributed Systems. IEEE Symposium on Reliable Distributed Systems, 2008, SRDS’08 (2008), IEEE), 259-268
[15] Kosa, M. J., Time bounds for strong and hybrid consistency for arbitrary abstract data types, Chic. J. Theor. Comput. Sci. (1999) · Zbl 0924.68081
[16] Kuhn, F.; Schmid, S.; Smit, J.; Wattenhofer, R., A blueprint for constructing peer-to-peer systems robust to dynamic worst-case joins and leaves, (14th IEEE International Workshop on Quality of Service. 14th IEEE International Workshop on Quality of Service, 2006, IWQoS 2006 (June 2006)), 12-19
[17] Kuhn, F.; Schmid, S.; Wattenhofer, R., A self-repairing peer-to-peer system resilient to dynamic adversarial churn, (Proceedings of the 4th International Conference on Peer-to-Peer Systems. Proceedings of the 4th International Conference on Peer-to-Peer Systems, IPTPS’05 (2005), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 13-23
[18] Leonard, D.; Rai, V.; Loguinov, D., On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks, ACM SIGMETRICS Perform. Eval. Rev., 33, 1, 26-37 (2005)
[19] Li, Z.; Parashar, M., Comet: a scalable coordination space for decentralized distributed environments, (Proceedings of the Second International Workshop on Hot Topics in Peer-to-Peer Systems. Proceedings of the Second International Workshop on Hot Topics in Peer-to-Peer Systems, HOT-P2P ’05 (2005), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 104-112
[20] Lynch, N.; Shvartsman, A., Rambo: a reconfigurable atomic memory service for dynamic networks, Distrib. Comput., 173-190 (2002) · Zbl 1029.68527
[21] Malkhi, D.; Reiter, M., Byzantine quorum systems, Distrib. Comput., 11, 4, 203-213 (1998) · Zbl 1448.68147
[22] McLaughry, S. W.; Wycko, P., T spaces: the next wave, (Proceedings of the Thirty-Second Annual Hawaii International Conference on System Sciences, vol. 8. Proceedings of the Thirty-Second Annual Hawaii International Conference on System Sciences, vol. 8, HICSS ’99 (1999), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 8037
[23] Merritt, M.; Taubenfeld, G., Computing with infinitely many processes, Distrib. Comput., 164-178 (2000) · Zbl 0987.68508
[24] Murphy, A.; Picco, G.; Roman, G., Lime: a middleware for physical and logical mobility, (Proceedings of the 21st International Conference on Distributed Computing Systems. Proceedings of the 21st International Conference on Distributed Computing Systems, ICDCS ’01 (2001), IEEE Computer Society: IEEE Computer Society Washington, DC, USA)
[25] Roh, H.; Jeon, M.; Kim, Jin-Soo; Lee, J., Replicated abstract data types: building blocks for collaborative applications, J. Parallel Distrib. Comput., 71, 3, 354-368 (March 2011)
[26] Schiper, A.; Raynal, M., A suite of formal definitions for consistency criteria in distributed shared memories, (ISCA Proceedings of the International Conference PDCS. ISCA Proceedings of the International Conference PDCS, Dijon, France (1996)), 125-130
[27] Schneider, F. B., Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Comput. Surv., 22, 4, 299-319 (1990)
[28] Shapiro, M.; Preguiça, N.; Baquero, C.; Zawirski, M., Conflict-free replicated data types, (Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems. Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS’11 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 386-400
[29] Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H., Chord: a scalable peer-to-peer lookup service for Internet applications, (Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM ’01 (2001), ACM: ACM New York, NY, USA), 149-160
[30] Thomas, R. H., A majority consensus approach to concurrency control for multiple copy databases, ACM Trans. Database Syst., 4, 2, 180-209 (June 1979)
[31] Tucci Piergiovanni, S.; Baldoni, R., Connectivity in eventually quiescent dynamic distributed systems, (Third Latin-American Symposium on Dependable Computing. Third Latin-American Symposium on Dependable Computing, LADC (2007), Springer), 38-56
[32] Voulgaris, S.; Gavidia, D.; Van Steen, M., Cyclon: inexpensive membership management for unstructured p2p overlays, J. Netw. Syst. Manag., 13, 2, 197-217 (2005)
[33] Wuu, G. T.J.; Bernstein, A. J., Efficient solutions to the replicated log and dictionary problems, (Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC ’84 (1984), ACM: ACM New York, NY, USA), 233-242
[34] Zhou, J.; Zhang, C.; Tang, H.; Wu, J.; Yang, T., Programming support and adaptive checkpointing for high-throughput data services with log-based recovery, (2010 IEEE/IFIP International Conference on Dependable Systems and Networks. 2010 IEEE/IFIP International Conference on Dependable Systems and Networks, DSN (2010), IEEE), 91-100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.