Grouping algorithms for scalable self-monitoring distributed systems

ABSTRACT

The growing complexity of distributed systems demands for new ways of control. Future systems should be able to adapt dynamically to the current conditions of their environment. They should be characterised by so-called self-x properties like self-configuring, self-healing, self-optimising, self-protecting, and context-aware. For the incorporation of such features typically monitoring components provide the necessary information about the system's state. In this paper we propose three algorithms which allow a distributed system to install monitoring relations among its components. This serves as a basis to build scalable distributed systems with self-x features and to achieve a self-monitoring capability. Evaluation measurements have been conducted to compare the proposed algorithms.

REFERENCES

• 1: C. Asavathiratham, S. Roy, B. Lesieutre, and G. Verghese. The influence model. Control Systems Magazine, IEEE, 21(6):52--64, Dec 2001.
• 2: B. S. Baker and R. Shostak. Gossips and telephones. Discrete Math., 2(3):191--193, June 1972.
• 3: M. Bertier, O. Marin, and P. Sens. Performance analysis of a hierarchical failure detector. In Proceedings 2003 International Conference on Dependable Systems and Networks (DSN 2003), pages 635--644, San Francisco, CA, USA, June 2003. IEEE Computer Society.
• 4: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 5: Abhinandan Das , Indranil Gupta , Ashish Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.303-312, June 23-26, 2002
• 6: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 7: Pascal Felber , Xavier Défago , Rachid Guerraoui , Philipp Oser, Failure Detectors as First Class Objects, Proceedings of the International Symposium on Distributed Objects and Applications, p.132, September 05-07, 1999
• 8: W. Feller. An Introduction to Probability Theory and its Application, Vol. 1. John Wiley and Sons, New York, 1970.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 10: Indranil Gupta , Tushar D. Chandra , Germán S. Goldszmidt, On scalable and efficient distributed failure detectors, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.170-179, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384010]
• 11: Y. Horita , K. Taura , T. Chikayama, A Scalable and Efficient Self-Organizing Failure Detector for Grid Applications, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.202-210, November 13-14, 2005 [doi>10.1109/GRID.2005.1542743]
• 12: P. Horn. Autonomic computing: Ibm's perspective on the state of information technology. http://www.research.ibm.com/autonomic/, 2001.
• 13: Jeffrey O. Kephart, Research challenges of autonomic computing, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062464]
• 14: Robbert Van Renesse , Yaron Minsky , Mark Hayden, A Gossip-Style Failure Detection Service, Cornell University, Ithaca, NY, 1998
• 15: U. Richter, M. Mnif, J. Branke, C. Müller-Schloer, and H. Schmeck. Towards a generic observer/controller architecture for organic computing. In C. Hochberger and R. Liskowsky, editors, INFORMATIK 2006 -- Informatik für Menschen, volume P-93 of GI-Edition -- Lecture Notes in Informatics, pages 112--119, Bonn, Germany, Sept. 2006. Köllen Verlag.
• 16: S. Roy, Y. Wan, and A. Saberi. Algorithmic Aspects of Wireless Sensor Networks, volume 4240/2006 of LNCS, chapter A Flexible Algorithm for Sensor Network Partitioning and Self-partitioning Problems, pages 152--163. Springer Berlin / Heidelberg, 2006.
• 17: Benjamin Satzger , Andreas Pietzowski , Wolfgang Trumler , Theo Ungerer, A new adaptive accrual failure detector for dependable distributed systems, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244129]
• 18: B. Satzger, A. Pietzowski, W. Trumler, and T. Ungerer. Variations and evaluations of an adaptive accrual failure detector to enable self-healing properties in distributed systems. In ARCS 2007, 20th International Conference, Zurich, Switzerland, March 12--15, 2007, volume 4415 of LNCS, pages 171--184. Springer, 2007.
• 19: Benjamin Satzger , Andreas Pietzowski , Wolfgang Trumler , Theo Ungerer, Using Automated Planning for Trusted Self-organising Organic Computing Systems, Proceedings of the 5th international conference on Autonomic and Trusted Computing, June 23-25, 2008, Oslo, Norway [doi>10.1007/978-3-540-69295-9_7]
• 20: H. Schmeck. Organic computing. Künstliche Intelligenz, 05(3):68--69, July 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms

Keywords:
algorithm, distributed system, failure detection, grouping, scalable, self-monitoring