Abstract
We consider the Group Membership Problem (GMP) in asynchronous systems. This problem consists of maintaining a list of processes belonging to the system, and updating it as processes join (are started) and leave (terminate or fail). Our investigations led to four independent properties that characterize instances of this problem. We closely examine three membership services, comparing the message cost to implement them, as well as their fault-tolerance and ability to adapt to environmental changes. We also examine their relative merits by comparing the cost to a distributed application that employs each of the membership services. We show that in typical system executions Strong GMP is less expensive to implement, is always more responsive to dynamic aspects in the environment, and allows applications to accomplish more work with less effort. As Strong GMP is the sole instance providing a linear order on membership changes, these results emphasize the benefits of providing Order as well as the cost of not providing it when it is available so cheaply.
Research supported by DARPA/NASA Ames Grant NAG 2-593, and by grants from IBM and Siemens Corporation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. El Abbadi, D. Skeen, and F. Cristian. An Efficient, Fault-Tolerant Algorithm for Replicated Data Management. In Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on the Principles of Database Systems, pages 215–229. A.C.M., 1985.
A. El Abbadi and S. Toueg. Availability in Partitioned Replicated Databases. In Proc. 5th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 240–251, Cambridge, MA, March 1986.
K. P. Birman and T. A. Joseph. Exploiting Virtual Synchrony in Distributed Systems. In Proceedings of the Eleventh ACM Symposium on Operating Systems Principles, 1987.
T. D. Chandra and S. Toueg. Unreliable Failure Detectors for Ashynchronous Systems. In Proceedings of the Tenth Annual A.C.M. Symposium on Principles of Distributed Computing. ACM, August 1991.
F. Cristian. Reaching Agreement on Processor Group Memberhsip in Synchronous Distributed Systems. Technical Report RJ 5964, IBM Almaden Research Center, August 1990. Revised from March, 1988.
M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossiblity of Distributed Consensus with One Faulty Process. Journal of the Association for Computing Machinery, 32(2):374–382, April 1985.
M. Herlihy. A Quorum-Consensus Replication Method for Abstract Data Types. ACM Transactions on Computer Systems, 1(4):32–53, 1986.
T. Joseph. Low Cost Management of Replicated Data. PhD thesis, Cornell University, 1986.
L. Lamport. Time, Clocks and the Ordering of Events in a Distributed System. Communications of the A.C.M., 21(7):558–565, 1978.
J. Meyer and R. Schlichting, editors. A Membership Protocol Based on Partial Order, volume 6 of Dependable Computing and Fault-Tolerant Systems, pages 309–331. Springer-Verlag, Vienna, 1992
A. Ricciardi and K. Birman. Using Process Groups to Implement Failure Detection in Asynchronous Environments. In Procedings of the Tenth Annual A.C.M. Symposium on Principles of Distributed Computing. A.C.M., August 19–21 1991. This is an extended abstract of Cornell University Technical Report TR91-1188, of the same name.
A. M. Ricciardi. Practical Utility of Knowledge-Based Analyses. In preparation, 1991.
A. M. Ricciardi. The Asynchronous Membership Problem. PhD thesis, Cornell University, September 1992.
A. M. Ricciardi. Practical Utility of Knowledge-Based Analyses: Optimizations and Optimality for and Implementation of Asynchronous Fail-Stop Processes. In Fourth Conference on the Theoretical Aspects of Reasoning About Knowlege. Morgan Kaufmann, March 22–25 1992.
P. Stephenson. Fast Ordered Multicastss. PhD thesis, Cornell University, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ricciardi, A., Birman, K., Stephenson, P. (1992). The cost of order in asynchronous systems. In: Segall, A., Zaks, S. (eds) Distributed Algorithms. WDAG 1992. Lecture Notes in Computer Science, vol 647. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56188-9_22
Download citation
DOI: https://doi.org/10.1007/3-540-56188-9_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56188-0
Online ISBN: 978-3-540-47484-5
eBook Packages: Springer Book Archive