A group membership service for large-scale grids

ABSTRACT

In this paper, we propose a decentralized group membership service that can be incorporated into existing grid middleware to make it more reliable. This service includes a flexible failure detector that adapts dynamically to changing network conditions and can be configured with a number of failure recovery strategies. Moreover, it disseminates information about membership changes (new processes, failures, etc.) in a scalable and efficient manner. We conducted a preliminary evaluation of the proposed service by simulating a grid with up to 140 nodes distributed across three domains separated by a wide-area network. This evaluation showed that the proposed service performs well both in the absence and in the presence of process failures.

REFERENCES

• 1: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 2: 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]
• 3: Wei Chen , Sam Toueg , Marcos Kawazoe Aguilera, On the Quality of Service of Failure Detectors, IEEE Transactions on Computers, v.51 n.5, p.561-580, May 2002 [doi>10.1109/TC.2002.1004595]
• 4: 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
• 5: 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]
• 6: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 7: Patrick T. Eugster , Rachid Guerraoui , Anne-Marie Kermarrec , Laurent Massoulieacute;, Epidemic Information Dissemination in Distributed Systems, Computer, v.37 n.5, p.60-67, May 2004 [doi>10.1109/MC.2004.1297243]
• 8: I. Foster and C. Kesselman. Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputing Applications, 2(11):115--128, 1997.
• 9: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: Andrei Goldchleger , Fabio Kon , Alfredo Goldman , Marcelo Finger , Germano Capistrano Bezerra, InteGrade object-oriented Grid middleware leveraging the idle computing power of desktop machines: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.5, p.449-459, April 2004 [doi>10.1002/cpe.v16:5]
• 11: A. Grimshaw , A. Ferrari , F. Knabe , M. Humphrey, Legion: An Operating System for Wide-Area Computing, University of Virginia, Charlottesville, VA, 1999
• 12: Naohiro Hayashibara , Xavier Defago , Rami Yared , Takuya Katayama, The " Accrual Failure Detector, Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems, p.66-78, October 18-20, 2004
• 13: 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]
• 14: S. Hwang and C. Kesselman. A flexible framework for fault tolerance in the grid. Journal of Grid Computing, 1(3):251--272, September 2003.
• 15: Roberto Ierusalimschy , Luiz Henrique de Figueiredo , Waldemar Celes Filho, Lua—an extensible extension language, Software—Practice & Experience, v.26 n.6, p.635-652, June 1996 [doi>10.1002/(SICI)1097-024X(199606)26:6<635::AID-SPE26>3.0.CO;2-P]
• 16: Amit Jain , R. K. Shyamasundar, Failure Detection and Membership Management in Grid Environments, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.44-52, November 08-08, 2004 [doi>10.1109/GRID.2004.30]
• 17: Joao Leitao , Jose Pereira , Luis Rodrigues, HyParView: A Membership Protocol for Reliable Gossip-Based Broadcast, Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, p.419-429, June 25-28, 2007 [doi>10.1109/DSN.2007.56]
• 18: R. Maia, R. Cerqueira, and R. Cosme. OiL: An object request broker in the Lua language. In Proc. 24th Brazilian Symposium on Computer Networks, 2006.
• 19: 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]
• 20: Xuanhua Shi , Hai Jin , Zongfen Han , Weizhong Qiang , Song Wu , Deqing Zou, ALTER: Adaptive Failure Detection Services for Grids, Proceedings of the 2005 IEEE International Conference on Services Computing, p.355-358, July 11-15, 2005 [doi>10.1109/SCC.2005.23]
• 21: P. Stelling , C. Lee , I. Foster , G. von Laszewski , C. Kesselman, A Fault Detection Service for Wide Area Distributed Computations, Proceedings of the 7th IEEE International Symposium on High Performance Distributed Computing, p.268, July 28-31, 1998
• 22: Tata Consulting Services. Wanem - the wide area network simulator. Last visit: August 2008 -- http://wanem.sourceforge.net/.
• 23: R. van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Proceedings of Middleware'1998, September 1998.

INDEX TERMS

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

General Terms:
Design, Reliability

Keywords:
failure detection, grid computing, group membership