The importance of benchmarking is increasing as every aspect of human life is relying on correct operation of computing systems. Although considerable efforts have been made, presently there are no widely accepted dependability benchmarks. The panelists, in the order shown above, address benchmarking of computer hardware, operating systems, applications, and systems.

We describe a benchmark for measuring system recovery on a nonclustered standalone system. A system's ability to recover from an outage quickly is a critical factor in overall system availability. General purpose computer systems, such as UNIX based systems, tend to execute the same sequence or series of steps during system startup and outage recovery. Our experience has shown that these steps are consistent, reproducible and measurable, and can thus be benchmarked. Additionally, the factors that create variability in restart/recovery can be bound and represented in a meaningful way. A defined set of measurements, coupled with a specification for representing the results and system variables, provide the foundation for system recovery benchmarking.

High availability clusters are becoming increasingly common in IT environments today, and the level of availability offered by such systems is a key factor used in their evaluation. However, no systematic and consistent methodology exists to perform such an assessment. Thus there is a critical need to establish cluster availability benchmarks. This paper proposes a cluster availability benchmark, SRB-X, that measures the automatic recovery time of a cluster framework in the event of a cluster node failure. SRB-X is a repeatable and portable benchmark, that measures a common outage mode for high availability clusters. After listing the main requirements of the underlying system recovery benchmark framework, this paper describes the various properties of SRB-X. The calculation of the SRB-X metric is illustrated through two examples.

This paper proposes a method to measure a specific aspect of a system's robustness - the handling of maintenance events. Past research in the area of robustness benchmarking has focused exclusively on injecting a realistic faultload into a system and examining the system's robustness against the set of injected faults. However, faults are not the only events that can cause a system outage. Maintenance events, such as the replacement of a failed hardware component or the installation of a software patch, may also result in a system outage. In this paper, we describe a benchmark for measuring a system's robustness against a class of hardware maintenance events.

An efficient fault simulation based evaluation methodology for the determination of fault coverages and test set quality is a practical way to obtain a set of high quality gate delay fault detecting tests. Unfortunately, the methodology is computationally intensive enough to be intractable for reasonably large VLSI circuits. An attractive alternative for speeding up these computation algorithms is parallel processing. In this paper, we present, for the first time, parallel algorithms for gate delay fault simulation and fault coverage determination through test quality evaluation. These algorithms are theoretically analyzed, and experimental studies of their implementation are reported. Studies of load balancing schemes for these algorithms are also presented. The results conform to the theoretically predicted performance, with speedups of up to 12 being obtained for 15 processors.

The class of NP-hard problems contains many problems of considerable practical importance. The complexity of these problems is so overwhelming that exhaustive search of the solution space is not possible even using massively parallel search techniques, particularly for problems of super-exponential complexity such as flow-shop and job-shop scheduling. This two-part paper discusses a novel, inherently parallel heuristic solution technique. Part I presents this technique, known as parallel dynamic interaction (PDI), as a general solution framework that is applicable to a number of computationally intractable problems, and gives details of its general methodology. From a parallel processing standpoint, PDI is interesting because it is inherently based upon the dynamic interplay between simultaneously executing subproblems. As such, PDI has no direct serial analog, and is not directly amenable to conventional parallel processing speedup analysis. This may provide an indication that parallel processing can offer opportunities beyond simply speeding up the solution of sequentially specified algorithms. From a practical problem-solving perspective, PDI shows promise as a method capable of generating high quality solutions to exponentially and super-exponentially hard problems. For large problems, PDI is often able to find a near-optimal solution many orders of magnitude faster than the time taken for a conventional parallel branch-and-bound search to find a solution of comparable quality.>

For pt.I. see ibid., p.1006-15. This paper presents the application of parallel dynamic interaction (PDI) to three real problem domains: the flowshop scheduling problem, the job-shop scheduling problem and the vertex cover problem. Specific examples are provided as to how the general PDI framework, introduced in part I of this paper, can be applied to a particular problem. The results of an empirical study of 90 example instances of these problems indicate that PDI consistently out-performs previously published heuristics for the vertex cover problem, and can typically generate solutions within a few percent of optimal for flow-shop and job-shop problems. Out of the 76 examples for which the optimal solution could be determined, PDI was able to produce results averaging within 4% of optimal. In over 30% of the cases, PDI was able to find the optimal solution. In no case did the PDI solution deviate more than 15% from optimal. It is also seen that the time taken by PDI to arrive at these solutions is negligible compared to that taken by conventional search techniques. This provides strong empirical evidence that PDI is capable of generating high quality solutions to exponentially and super-exponentially hard problems in reasonably short periods of time.>

Delay testing continues to gain importance as manufacturers try to meet stricter requirements for higher performance and higher density integrated circuits. The methodology to obtain a set of high quality gate delay fault detecting tests is unfortunately computationally intensive enough to be intractable for reasonably large VLSI circuits; parallelization of these computations is thus an attractive scenario. We present, for the first time, distributed algorithms for gate delay fault simulation and fault coverage determination through test quality evaluation. These algorithms are implemented over a network of workstations, which is normally available at most design labs, and thus do not rely os the use of very specialized, expensive, or difficult-to-access hardware. These algorithms are theoretically analyzed, and experimental studies of their implementation are reported. The results conform to the theoretically predicted performance, with speedups of up to 10 being obtained with 15 workstations.>

This paper proposes and analyzes a parallel implementation of the matrix product algorithm for the all pairs shortest path problem for a distributed memory MIMD model. The results of experiments conducted on a 128-processor hypercube machine show that the parallel implementation achieves the performance predicted by the analysis.>

This paper proposes two distributed solutions to the all-pairs shortest path problem, and reports the results of experiments conducted on a network of IBM RISC System/6000s, containing up to seven such workstations. It discusses the issues that become critical in a distributed environment as opposed to a parallel environment, and the results obtained underline the importance of reducing communication between the loosely coupled subtasks in a distributed environment. The results demonstrate that properly designed distributed algorithms, which take into account the limitations (in terms of a slower communication medium and/or the non-dedicated mode of machines) of a distributed computing environment, can yield significant performance benefits.>