© 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Networking
Volume 6 Number 5, October 1998

Table of Contents for this issue

Complete paper in PDF format

An Evaluation of Flow Control in Group Communication

Shivakant Mishra and Lei Wu, Member, IEEE

Page 571.

Abstract:

Group communication services have been successfully used to construct applications with high availability, dependability, and real-time responsiveness requirements. Flow-control techniques enable group members to manage their local buffers, which they use to temporarily store multicast updates. Despite buffer overflow being one of the main causes of process failures, flow control has not been studied much in literature. We study different flow-control techniques used in some of the group communication services and present two generic flow-control techniques: a conservative and an optimistic technique. All existing flow-control techniques for group communication can be classified as either conservative or optimistic. We then present discrete event simulation results that compare the effect of these two generic flow-control techniques on the performance of two different atomic multicast protocols, a positive acknowledgment protocol and a negative acknowledgment protocol, under several different operating conditions. Based on the study of different existing flow-control techniques for group communication and the results obtained from the simulation experiment, we provide some design guidelines for the design and implementation of a suitable flow-control technique for a given group communication service.

References

  1. G. A. Alvarez, F. Cristian, and S. Mishra, "On-demand asynchronous atomic broadcast," in Proc. Fifth IFIP Int. Conf. on Dependable Computing for Critical Applications, Urbana-Champaign, IL, Sept. 1995.
  2. Y. Amir, D. Dolev, S. Kramer, and D. Malki, "Transis: A communication sub-system for high availability," in Proc. 22nd International Symp. on Fault-Tolerant Computing, Boston, MA, July 1992, pp. 76-84.
  3. Y. Amir, L. Moser, P. Melliar-Smith, D. Agarwal, and P. Ciarfella, "The totem single-ring ordering and membership protocol," ACM Trans. Comput. Syst., vol. 13, no. 4, pp. 311-342, 1995.
  4. K. Birman, A. Schiper, and P. Stephenson, "Lightweight causal and atomic group multicast," ACM Trans. Comput. Syst., vol. 9, no. 3, pp. 272-314, Aug. 1991.
  5. R. Carr, "The Tandem global update protocol," Tandem Systems Rev., June 1985.
  6. J. Chang and N. Maxemchuk, "Reliable broadcast protocols," ACM Trans. Comput. Syst., vol. 2, no. 3, pp. 251-273, Aug. 1984.
  7. F. Cristian, "Asynchronous atomic broadcast," IBM Tech. Disclosure Bull., vol. 33, no. 9, pp. 115-116, Feb. 1991.
  8. --, "Understanding fault-tolerant distributed systems," Commun. ACM, vol. 34, no. 2, pp. 56-78, Feb. 1991.
  9. F. Cristian, R. de Beijer, and S. Mishra, "Comparing how well asynchronous atomic broadcast protocols perform," in Proc. Third Int. Workshop on Responsive Computer Systems, Lincoln, NH, Sept. 1993, pp. 192-204.
  10. --, "A performance comparison of asynchronous atomic broadcast protocols," Distrib. Syst. Eng., vol. 1, no. 4, pp. 177-201, June 1994.
  11. F. Cristian and S. Mishra, "The pinwheel asynchronous atomic broadcast protocols," in Proc. Second Int. Symp. on Autonomous Decentralized Systems, Phoenix, AZ, Apr. 1995, pp. 215-221.
  12. F. Cristian, S. Mishra, and G. Alvarez, "High-performance asynchronous atomic broadcast," Distrib. Syst. Eng., vol. 4, no. 2, pp. 109-128, June 1997.
  13. T. Hickey and R. van Renesse, "Incorporating system resource information into flow control," Tech. Rep. TR 95-1489, Dep. Computer Science, Cornell University, Ithaca, NY, 1995.
  14. M. F. Kaashoek and A. Tanenbaum, "Group communication in the amoeba distributed operating system," in Proc. 11th Int. Conf. on Distributed Computing Systems, Arlington, TX, May 1991, pp. 222-230.
  15. M. F. Kaashoek, A. Tanenbaum, S. F. Hummel, and H. Bal, "An efficient reliable broadcast protocol," Operating Syst. Rev., vol. 23, no. 4, pp. 5-19, Oct 1989.
  16. L. Lamport, "Time, clocks, and the ordering of events in a distributed system," Commun. ACM, vol. 21, no. 7, pp. 558-565, July 1978.
  17. S. Mishra, C. Fetzer, and F. Cristian, "The timewheel asynchronous atomic broadcast protocol," in Proc. 1997 Int. Conf. on Parallel and Distributed Processing Techniques and Applications, Las Vegas, NV, June 1997, pp. 1239-1248.
  18. --, "The timewheel group membership protocol," in Proc. Workshop on Fault Tolerant Parallel and Distributed Systems, Orlando, FL, Apr. 1998.
  19. S. Mishra, L. Peterson, and R. Schlichting, "Consul: A communication substrate for fault-tolerant distributed programs," Distrib. Syst. Eng., vol. 1, no. 2, pp. 87-103, Dec. 1993.
  20. M. K. Molloy, Fundamentals of Performance Modeling.New York: Macmillan, 1989.
  21. L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, R. K. Budhia, and C. A. Lingley-Papadopoulos, "Totem: A fault-tolerant multicast group communication system," Commun. ACM, vol. 39, no. 4, pp. 54-63, Apr. 1996.
  22. D. Powell, Ed., Delta-4: A Generic Architecture for Dependable Distributed Computing.Vienna, Austria: Springer-Verlag, 1991.
  23. L. Rodrigues and P. Verissimo, "xAMp: A multi-primitive group communications service," Tech. Rep., INESC, Lisbon, Portugal, Sept. 1991.
  24. F. Schneider, "Implementing fault-tolerant services using the state machine approach: A tutorial," ACM Comput. Surveys, vol. 22, no. 4, pp. 299-319, Dec. 1990.
  25. R. van Renesse, K. Birman, R. Friedman, M. Hayden, and D. Karr, "A framework for protocol composition in horus," presented at the 14th ACM Symp. on Principles of Distributed Computing, Aug. 1995.
  26. R. van Renesse, K. Birman, and S. Maffeis, "Horus: A flexible group communication system," Commun. ACM, vol. 39, no. 4, pp. 76-83, Apr. 1996.
  27. P. Verissimo and J. Marques, "Reliable broadcast for fault-tolerance on local computer networks," in Proc. Ninth Symp. on Reliable Distributed Systems, Huntsville, AL, Oct. 1990, pp. 54-63.