15604810
Fault-tolerant grid services using primary-backup: feasibility and performance
The combination of grid technology and Web services has produced an attractive platform for deploying distributed applications: grid services, as represented by the Open Grid Services Infrastructure (OGSI) and its Globus toolkit implementation. As the use of grid services grows in popularity, tolerating failures becomes increasingly important. This work addresses the problem of building a reliable and highly-available grid service by replicating the service on two or more hosts using the primary-backup approach. The primary goal is to evaluate the ease and efficiency with which this can be done, by first designing a primary-backup protocol using OGSI, and then implementing it using Globus to evaluate performance implications and tradeoffs. We compared three implementations: one that makes heavy use of the notification interface defined in OGSI, one that uses standard grid service requests instead of notification, and one that uses low-level socket primitives. The overall conclusion is that, while the performance penalty of using Globus primitives - especially notification - for replica coordination can be significant, the OGSI model is suitable for building highly-available services and it makes the task of engineering such services easier.
10589983
Group membership and wide-area master-worker computations
Group communications systems have been designed to provide an infrastructure for fault-tolerance in distributed systems, including wide-area systems. In our work on master-worker computation for GriPhyN, which is a large project in the area of the computational grid, we asked the question should we build our wide-area master-worker computation using wide-area group communications? This paper explains why we decided doing so was not a good idea.
18569940
Segmentation of bright targets using wavelets and adaptive thresholding
A general systematic method for the detection and segmentation of bright targets is developed. We use the term "bright target" to mean a connected, cohesive object which has an average intensity distribution above that of the rest of the image. We develop an analytic model for the segmentation of targets, which uses a novel multiresolution analysis in concert with a Bayes classifier to identify the possible target areas. A method is developed which adaptively chooses thresholds to segment targets from background, by using a multiscale analysis of the image probability density function (PDF). A performance analysis based on a Gaussian distribution model is used to show that the obtained adaptive threshold is often close to the Bayes threshold. The method has proven robust even when the image distribution is unknown. Examples are presented to demonstrate the efficiency of the technique on a variety of targets.
3597789
Efficient forward computation of dynamic slices using reduced ordered binary decision diagrams
Dynamic slicing algorithms can greatly reduce the debugging effort by focusing the attention of the user on a relevant subset of program statements. Recently, algorithms for forward computation of dynamic slices have been proposed which maintain dynamic slices of all variables as the program executes. An advantage of this approach is that when a request for a slice is made, it is already available. The main disadvantage of using such an algorithm for slicing realistic programs is that the space and time required to maintain a large set of dynamic slices corresponding to all program variables can be very high. In this paper, we analyze the characteristics of dynamic slices and identify properties that enable space efficient representation of a set of dynamic slices. We show that by using reduced ordered binary decision diagrams (roBDDs) to represent a set of dynamic slices, the space and time requirements of maintaining dynamic slices are greatly reduced. In fact, not only can the latest dynamic slices of all variables be easily maintained, but rather all dynamic slices of all variables throughout a program's execution can be maintained. Our experiments show that our roBDD based algorithm for forward computation of dynamic slices can maintain 107-217 million dynamic slices arising during long program runs using only 28-392 megabytes of storage. In addition, the performance of the roBDD based forward computation method compares favorably with the performance of the LP backward computation algorithm.
2953976
A performance study of monitoring and information services for distributed systems
Monitoring and information services form a key component of a distributed system, or Grid. A quantitative study of such services can aid in understanding the performance limitations, advise in the deployment of the monitoring system, and help evaluate future development work. To this end, we study the performance of three monitoring and information services for distributed systems: the Globus Toolkit/spl reg/ Monitoring and Discovery Service (MDS2), the European Data Grid Relational Grid Monitoring Architecture (R-GMA) and Hawkeye, part of the Condor project. We perform experiments to test their scalability with respect to number of users, number of resources and amount of data collected. Our study shows that each approach has different behaviors, often due to their different design goals. In the four sets of experiments we conducted to evaluate the performance of the service components under different circumstances, we found a strong advantage to caching or pre-fetching the data, as well as the need to have primary components at well-connected sites because of the high load seen by all systems.
519875
Virtual Clusters for Grid Communities
A challenging issue facing Grid communities is that while Grids can provide access to many heterogeneous resources, the resources to which access is provided often do not match the needs of a specific application or service. In an environment in which both resource availability and software requirements evolve rapidly, this disconnect can lead to resource underutilization, user frustration, and much wasted effort spent on bridging the gap between applications and resources. We show here how these issues can be overcome by allowing authorized Grid clients to negotiate the creation of virtual clusters made up of virtual machines configured to suit client requirements for software environment and hardware allocation. We introduce descriptions and methods that allow us to deploy flexibly configured virtual cluster workspaces. We describe their configuration, implementation, and evaluate them in the context of a virtual cluster representing the environment in production use by the Open Science Grid. Our performance evaluation results show that virtual clusters representing current Grid production environments can be deployed and managed efficiently, and thus can provide an acceptable platform for Grid applications.
18753637
Fast factorization architecture in soft-decision Reed-Solomon decoding
Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.