Abstract
This research direction aims to develop and analyze algorithms to solve problems of communication and data sharing in highly dynamic distributed environments. The term dynamic here encompasses many types of changes, including changing network topology, processor mobility, changing sets of participating client processes, a wide range of types of processor and network failures, and timing variations. Constructing distributed applications for such environments is a difficult programming problem. In practice, considerable effort is required to make applications resilient to changes in client requirements and to evolution of the underlying computing medium. We focus our work on distributed services that provide useful guarantees and that make the construction of sophisticated distributed applications easier. The properties we study include ordering and reliability guarantees for communication and coherence guarantees for data sharing. To describe inherent limitations on what problems can be solved, and at what cost, the algorithmic results will be accompanied by lower bound and impossibility results. One example of our approach is the new dynamic atomic shared-memory service for message-passing systems. We formally specified the service and developed algorithms implementing the service. A system implementation is under development. The service is reconfigurable in the sense that the set of owners of data can be changed dynamically and concurrently with the ongoing read and write operations.
This work is supported by the NSF Grants 0121277, 9988304 and 9984774.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Attiya, A. Bar-Noy and D. Dolev, “Sharing Memory Robustly in Message Passing Systems”, J. of the ACM, vol. 42, no. 1, pp. 124–142, 1996.
Kenneth P. Birman. A review of experiences with reliable multicast. Software, Practice and Experience, 29(9):741–774, September 1999.
O. Cheiner and A. Shvartsman, “Implementing an eventually-serializable data service as a distributed system building block,” in Networks in Distributed Computing, vol. 45, pp. 43–72, AMS.
R. De Prisco, A. Fekete, N. Lynch, and A. Shvartsman, “A dynamic primary configuration group communication service,” in Distributed Computing Proceedings of DISC’99-13th International Symposium on Distributed Computing, 1999, LNCS, vol. 1693, pp. 64–78.
B. Englert and A. Shvartsman. Graceful quorum reconfiguration in a robust emulation of shared memory. In Proc. of the 20th IEEE Int-l Conference on Distributed Computing Systems (ICDCS’2000), pp. 454–463, 2000.
A. Fekete, D. Gupta, V. Luchangco, N. Lynch, and A. Shvartsman, “Eventually-serializable data service,” Theoretical Computer Science, vol. 220, no. 1, pp. 113–156, June 1999.
A. Fekete, N. Lynch, and A. Shvartsman. “Specifying and using a partitionable group communication service.” ACM Trans. on Computer Systems. vol. 19, no. 2, pp. 171–216, 2001.
R. Guerraoui and A. Schiper, “The Generic Consensus Service,” IEEE Trans. on Software Engineering, Vol. 27, No. 1, pp. 29–41, January, 2001.
S. Haldar and P. Vitányi, “Bounded Concurrent Timestamp Systems UsingVector Clocks”, J. of the ACM,Vol. 249, No. 1, pp. 101–126, January, 2002
Leslie Lamport, “The Part-Time Parliament”, ACM Transactions on Computer Systems, 16(2) 133–169, 1998.
N. Lynch and A. Shvartsman, “RAMBO: A Reconfigurable Atomic Memory Service”, in Proc. of 16th Int-l Symposium on Distributed Computing, DISC’2002, pp. 173–190, 2002.
K. W. Ingols, “Availability study of dynamic voting algorithms,” M.S. thesis, Dept. of Electrical Engineering and Computer Science, MIT, May 2000.
M. Merritt and G. Taubenfeld, “Computing with infinitely many processes (under assumptions on concurrency and participation),” In Proc.14th International Symposium on DIStributed Computing (DISC), October 2000.
E. Yeger Lotem, I. Keidar, and D. Dolev. “Dynamic voting for consistent primary components.” In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pages 63–71, August 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Lynch, N., Shvartsman, A. (2003). Communication and Data Sharing for Dynamic Distributed Systems. In: Schiper, A., Shvartsman, A.A., Weatherspoon, H., Zhao, B.Y. (eds) Future Directions in Distributed Computing. Lecture Notes in Computer Science, vol 2584. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37795-6_12
Download citation
DOI: https://doi.org/10.1007/3-540-37795-6_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00912-2
Online ISBN: 978-3-540-37795-5
eBook Packages: Springer Book Archive