# Presentation: 301555

## Algorithm-Dependent Fault Tolerancefor Distributed Computing

- P. D. Hough
- M. E. Goldsby, T. G. Kolda, E. J. Walsh
- Sandia National Laboratories, CA
- A. D. George
- M. C. Chidester, R. El-Kadi, B. Nguyen,
- S. Ranganathan, R. W. Todd
- HCS Research Laboratory, University of Florida
- V. Torczon
- College of William and Mary

## Fault tolerance for Cplant-like systems is critical for a production environment

- Large-scale simulations
- run for days
- crash in the event of a failure
- Large heterogeneous cluster systems assembled from commodity parts
- diverse processor technologies and network topologies
- no support for fault tolerance from manufacturers

**In a large-scale cluster system, failures are likely to occur.  The goal of fault tolerance is to effectively detect and deal with these failures.**

## A materials characterization problem using ALEGRA would require several days of compute time

- Materials characterization is formulated as an optimization problem
- Each ALEGRA run takes 30 minutes
- An optimization algorithm would require a minimum of 11 iterations
- 11 ALEGRA calls for function values
- 121 ALEGRA calls for derivatives

**The goal of the materials characterization**
**problem is to determine material parameters**
**that will yield computational results that most**
**closely match experimental results.**

## The number of processors available on Cplant can vary from day to day

## These failures can occur anywhere in the system

## Fault tolerance consists of two primary components, embedded in three software layers

- Fault detection
- group membership protocols
- based on broadcasts
- gossip-based protocols
- selected point-to-point communication
- Fault recovery
- transparent to the user
- requires replication or full checkpointing
- application-dependent
- takes advantage of algorithmic properties

## Gossip-based protocols work much like Sandia

**      ****Did you hear?  Gil Weigand retired!**

**Juan Meza is infiltrating DOE!**

**Fault tolerance**
**is a great project!**

**We have to cut **
**back on travel!**

**John Larson is**
**leaving CA!**

## In other words, processes rely on information from other processes

- Each process has information regarding the state of the entire distributed system
- Each process periodically chooses a process with which to share its information
- New information is merged with existing information to obtain an updated state

## University of Florida detection protocols have been improved and extended

- Optimized gossip protocols
- minimize number of false detections
- make best use of bandwidth
- Scalable consensus algorithm
- Software implementation running on 90+ nodes
- New report
- S. Ranganathan, A. D. George, R. W. Todd, M. C. Chidester, “Gossip-Style Failure Detection and Distributed Consensus for Scalable Heterogeneous Clusters”, submitted to *Cluster Computing*.

## Gossip protocol improvements are accomplished by round-robin communication

**1st Round**

**2nd Round**

**3rd Round**

**4th Round**

**5th Round**

## New gossip protocol performs better than previous versions

## Asynchronous Parallel Pattern Search (APPS) optimization is ideally suited for fault tolerance

- Fault tolerance characteristics
- can tolerate some information loss
- can add and remove processors on the fly
- can restart processes with very little overhead
- no single point of failure
- Successful on applications
- e.g., characterization of an electrical circuit (collaboration with Ken Marx)

- Asynchronous Parallel Pattern Search

**Pattern search methods optimize a function**
**by considering only the function value at**
**intelligently chosen points in space.**

## Slide 13

## APPS, even with faults, compares favorably to the synchronous PPS

## APPS has also received external recognition

- Code ready for release as APPSPACK 1.0
- Requests
- NEOS optimization server
- article for *SIAM News*
- Numerous presentations
- Technical report submitted for publication
- P. D. Hough, T. G. Kolda, and V. Torczon, “Asynchronous Parallel Pattern Search for Nonlinear Optimization”, SAND2000-8213, submitted to *SIAM Journal on Scientific Computing.*

## We have implemented a fault-tolerant version of the Infrastructure for Distributed Enterprise Simulation (IDES)

- Fault tolerance characteristics
- requires all information
- natural synchronization point
- can accept communication from externals
- written in Java
- runs on a fixed number of nodes
- Report in progress
- M. E. Goldsby, “Adding Fault Tolerance to Distributed Java Programs”

**The Infrastructure for Distributed Enterprise**
**Simulation (IDES) is a parallel discrete event**
**simulation framework capable of handling**
**massive enterprise simulations with large**
**numbers of simulation entities.  It is used for**
**simulations of the nuclear weapons complex.**

## A new FT interface facilitates introducing fault tolerance into IDES and allows generality

**FT**

## Future Work:  FY00

- Evaluate impact of detection services on resources (and vice versa)
- Address restart issues in APPS
- Investigate SMP and I/O issues
- Investigate an agent-based solution

## Future Work:  FY01

- Incorporate new ideas into detection services
- Extend FT interface
- Incorporate communication layer
- New applications
- COMPASS
- Lilith
- Simulation Intranet