BACKGROUND: The PubMed archive contains more than 34 million articles; consequently, it is becoming increasingly difficult for a biomedical researcher to keep up-to-date with different knowledge domains. Computationally efficient and interpretable tools are needed to help researchers find and understand associations between biomedical concepts. The goal of literature-based discovery (LBD) is to connect concepts in isolated literature domains that would normally go undiscovered. This usually takes the form of an A-B-C relationship, where A and C terms are linked through a B term intermediate. Here we describe Serial KinderMiner (SKiM), an LBD algorithm for finding statistically significant links between an A term and one or more C terms through some B term intermediate(s). The development of SKiM is motivated by the observation that there are only a few LBD tools that provide a functional web interface, and that the available tools are limited in one or more of the following ways: (1) they identify a relationship but not the type of relationship, (2) they do not allow the user to provide their own lists of B or C terms, hindering flexibility, (3) they do not allow for querying thousands of C terms (which is crucial if, for instance, the user wants to query connections between a disease and the thousands of available drugs), or (4) they are specific for a particular biomedical domain (such as cancer). We provide an open-source tool and web interface that improves on all of these issues. RESULTS: We demonstrate SKiM's ability to discover useful A-B-C linkages in three control experiments: classic LBD discoveries, drug repurposing, and finding associations related to cancer. Furthermore, we supplement SKiM with a knowledge graph built with transformer machine-learning models to aid in interpreting the relationships between terms found by SKiM. Finally, we provide a simple and intuitive open-source web interface ( https://skim.morgridge.org ) with comprehensive lists of drugs, diseases, phenotypes, and symptoms so that anyone can easily perform SKiM searches. CONCLUSIONS: SKiM is a simple algorithm that can perform LBD searches to discover relationships between arbitrary user-defined concepts. SKiM is generalized for any domain, can perform searches with many thousands of C term concepts, and moves beyond the simple identification of an existence of a relationship; many relationships are given relationship type labels from our knowledge graph.

Scientists using the high-throughput computing (HTC) paradigm for scientific discovery rely on complex software systems and heterogeneous architectures that must deliver robust science (i.e., ensuring performance scalability in space and time; trust in technology, people, and infrastructures; and reproducible or confirmable research). Developers must overcome a variety of obstacles to pursue workflow interoperability, identify tools and libraries for robust science, port codes across different architectures, and establish trust in non-deterministic results. This poster presents recommendations to build a roadmap to overcome these challenges and enable robust science for HTC applications and workflows. The findings were collected from an international community of software developers during a Virtual World Cafe in May 2021.

The growing number of remote sensing data create more opportunity for scientific studies in various disciplines, along with new challenges to data processing techniques. Most of existing solutions show limitations at either throughput or automation level. In this paper, we propose an efficient framework for building and dynamically managing remote sensing data processing workflows in a distributed high-throughput environment. We use HTCondor system to allocate computing resource and schedule tasks while developing Python modules for processing operations and workflow management. The proposed framework not only illustrate a general way to process mass remote sensing data in a high-throughput manner but also demonstrates a novel solution to dynamically manage scientific workflows in the HTCondor system.

The user of a computing facility must make a critical decision when submitting jobs for execution: how many resources (such as cores, memory, and disk) should be requested for each job? If the request is too small, the job may fail due to resource exhaustion; if the request is too large, the job may succeed, but resources will be wasted. This decision is especially important when running hundreds of thousands of jobs in a high throughput workflow, which may exhibit complex, long tailed distributions of resource consumption. In this paper, we present a strategy for solving the job sizing problem: (1) applications are monitored and measured in user-space as they run; (2) the resource usage is collected into an online archive; and (3) jobs are automatically sized according to historical data in order to maximize throughput or minimize waste. We evaluate the solution analytically, and present case studies of applying the technique to high throughput physics and bioinformatics workflows consisting of hundreds of thousands of jobs, demonstrating an increase in throughput of 10-400 percent compared to naive approaches.

Robust high throughput computing requires effective monitoring and enforcement of a variety of resources including CPU cores, memory, disk, and network traffic. Without effective monitoring and enforcement, it is easy to overload machines, causing failures and slowdowns, or underutilize machines, which results in wasted opportunities. This paper explores how to describe, measure, and enforce resources used by computational tasks. We focus on tasks running in distributed execution systems, in which a task requests the resources it needs, and the execution system ensures the availability of such resources. This presents two non-trivial problems: how to measure the resources consumed by a task, and how to monitor and report resource exhaustion in a robust and timely manner. For both of these tasks, operating systems have a variety of mechanisms with different degrees of availability, accuracy, overhead, and intrusiveness. We describe various forms of monitoring and the available mechanisms in contemporary operating systems. We then present two specific monitoring tools that choose different tradeoffs in overhead and accuracy, and evaluate them on a selection of benchmarks.

SCMSWeb-Condor interface development is an international collaborative effort among some PRAGMA member institutions (ThaiGrid, Thailand; KISTI, Korea; SDSC, USA) and Condor team at University of Wisconsin. It aims at utilizing the rich information collected by the grid monitoring system - SCMSWeb, to enable Condor-G to provide more intelligent grid-level scheduling services. This paper addresses the motivations, practices, benefits and issues of this collaboration; illustrates the design, development and implementation of the SCMSWeb-Condor interface; describes the experiences, test results and discussions driven by running applications thru the SCMSWeb-Condor interface.

Utility grids such as the Amazon EC2 cloud and Amazon S3 offer computational and storage resources that can be used on-demand for a fee by compute and data-intensive applications. The cost of running an application on such a cloud depends on the compute, storage and communication resources it will provision and consume. Different execution plans of the same application may result in significantly different costs. Using the Amazon cloud fee structure and a real-life astronomy application, we study via simulation the cost performance tradeoffs of different execution and resource provisioning plans. We also study these trade-offs in the context of the storage and communication fees of Amazon S3 when used for long-term application data archival. Our results show that by provisioning the right amount of storage and compute resources, cost can be significantly reduced with no significant impact on application performance.

No abstract available.

The grid vision of a single computing utility has yet to materíalize: while many grids with thousands of processors each exist, most work in isolation. An important obstacle for the effective and efficient inter-operation of grids is the problem of resource selection. In this paper we propose a solution to this problem that combines the hierarchical and decentralized approaches for interconnecting grids. In our solution, a hierarchy of grid sites is augmented with peer-to-peer connections between sites under the same administrative control. To operate this architecture, we employ the key concept of delegated matchmaking, which temporarily binds resources from remote sites to the local environment. With trace-based simulations we evaluate our solution under various infrastructural and load conditions, and we show that it outperforms other approaches to inter-operating grids. Specifically, we show that delegated matchmaking achieves up to 60% more goodput and completes 26% more jobs than its best alternative.

Consider a workload in which massively parallel tasks that require large resource pools are interleaved with short tasks that require fast response but consume fewer resources. We aim at achieving high throughput and short response time when scheduling such a workload over a set of uncoordinated grids of varying sizes and performance characteristics. We propose the concept of a grid execution hierarchy, where available grids are sorted according to their size, and the execution overheads increase with the size of the grids. We devise a scheduling algorithm for this execution hierarchy of grids by adapting the multilevel feedback queue approach to a multi-grid environment. The algorithm finds a grid of the size, availability, and overhead that best matches a task's resource requirements and expected turnaround time. Our approach is inspired by the shortest processing time first policy (SPTF), in the sense that the task's processing demands are constantly reevaluated during its run, so that a task is migrated to a more suitable level of the execution hierarchy when appropriate. We evaluate our approach in the context of the superlink-online system for processing genetic linkage analysis tasks - a production system consisting of several grids and utilizing tens of thousands of CPU hours a month. With our approach the system provides nearly interactive response time for shorter tasks, while simultaneously serving throughput-oriented massively parallel tasks in an efficient manner

Grids are becoming a mission-critical component in research and industry. The services they provide are thus required to be highly available, contributing to the vision of the grid as a dependable virtual computer of infinite power. However, building highly available services in grid is particularly difficult due to the unique characteristics of the grid environment. We believe that high availability functionality should itself be provided as a service, which can be used by transparently decorating, but not changing, the original services, thus making them highly available. In this work we highlight the major challenges and describe our initial experience in building such a generic high availability service in the context of the Condor system

Abstract In this paper, we examine the issues of workflow mapping and execution in opportunistic environments such as the Grid. As applications become ever more complex, the process of choosing the appropriate resources and successfully executing the application components becomes ever more difficult. This may include extension or reduction of the initial workflow mapping as necessary for the actual execution. In this paper, we focus on the interplay between a workflow‐mapping component that plans the high‐level resource assignments and the workflow executor that oversees the component execution. We concentrate particularly on issues of data management and we draw from the experiences with mapping and execution systems: Pegasus, DAGMan and Stork. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Grid computing promises access to large amounts of computing power, but so far adoption of Grid computing has been limited to highly specialized experts for three reasons. First, users are used to batch systems, and interfaces to Grid software are often complex and different to those in batch systems. Second, users are used to having transparent file access, which Grid software does not conveniently provide. Third, efforts to achieve wide‐spread coordination of computers while solving the first two problems is hampered when clusters are on private networks. Here we bring together a variety of software that allows users to almost transparently use Grid resources as if they were local resources while providing transparent access to files, even when private networks intervene. As a motivating example, the BaBar Monte Carlo production system is deployed on a truly distributed environment, the European DataGrid, without any modification to the application itself. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Scientific distributed applications have an increasing need to process and move large amounts of data across wide area networks. Existing systems either closely couple computation and data movement, or they require substantial human involvement during the end‐to‐end process. We propose a framework that enables scientists to build reliable and efficient data transfer and processing pipelines. Our framework provides a universal interface to different data transfer protocols and storage systems. It has sophisticated flow control and recovers automatically from network, storage system, software and hardware failures. We successfully used data pipelines to replicate and process three terabytes of DPOSS astronomy image dataset and several terabytes of WCER educational video dataset. In both cases, the entire process was performed without any human intervention and the data pipeline recovered automatically from various failures. Copyright © 2005 John Wiley & Sons, Ltd.

How can we measure the impact of an open-source software package over time? When a system has no price, no purchase contracts and no buyers or sellers it can be difficult to judge its impact on the world. To explore this issue, we have instrumented the Condor distributed batch system in a variety of ways and observed its growth to over 50 000 CPUs at over 1000 sites over five years. Instrumentation methods include automatic updates by e-mail and user datagram protocol (UDP), annotated download records and a voluntary user survey. Each of these metrics has various strengths and weaknesses that we are able to compare and contrast. We also explore the ethical and legal issues surrounding automatic data collection. Surprisingly, we discover that objections to automatic data collection are higher among people that are not using the Condor software. We conclude with some practical advice for further research into the measurement of software systems. Copyright © 2006 John Wiley & Sons, Ltd.

Firewalls/NATs have brought significant connectivity problems along with their benefits, causing many applications to break or become inefficient. Due to its bi-directional communication, huge scale, and multi-organizational nature, the grid may be one of the areas damaged most by the connectivity problem. Several ideas to deal with the connectivity problem were investigated and many systems are available. However, many issues still remain unanswered. Most systems are firewall/NAT unfriendly and are considered harmful to network security; the tussle between these devices trying to investigate pay loads and applications trying to protect their content from observation and modification must be reconciled. This paper discusses how a simple relay-based system, called XRAY (middlebox traversal by relaying), deals with these issues and provides other benefits such as flexible traffic control. This paper also discusses how relay-based traversal systems can help applications to communicate over firewalls/NATs and also complement firewall/NAT operations to help network security

Firewalls and network address translators (NATs) cause significant connectivity problems along with benefits such as network protection and easy address planning. Connectivity problems make nodes separated by a firewall/NAT unable to communicate with each other. Due to the bidirectional and multi-organizational nature of grids, they are particularly susceptible to connectivity problems. These problems make collaboration difficult or impossible and cause resources to be wasted. This paper presents a system, called CODO, which provides applications end-to-end connectivity over firewalls/NATs in a secure way. CODO allows applications authorized through strong security mechanisms to traverse firewalls/NATs, while blocking unauthorized applications. This paper also formalizes the firewall/NAT traversal problem and clarifies how a traversal system fits in the overall security policy enforcement by a firewall/NAT.

Abstract Since 1984, the Condor project has enabled ordinary users to do extraordinary computing. Today, the project continues to explore the social and technical problems of cooperative computing on scales ranging from the desktop to the world‐wide computational Grid. In this paper, we provide the history and philosophy of the Condor project and describe how it has interacted with other projects and evolved along with the field of distributed computing. We outline the core components of the Condor system and describe how the technology of computing must correspond to social structures. Throughout, we reflect on the lessons of experience and chart the course travelled by research ideas as they grow into production systems. Copyright © 2005 John Wiley & Sons, Ltd.

Grid computing brings with it additional complexities and unexpected failures. Just keeping track of our jobs traversing different grid resources before completion can at times become tricky. We introduce a client-centric grid knowledgebase that keeps track of the job performance and failure characteristics on different grid resources as observed by the client. We present the design and implementation of our prototype grid knowledgebase and evaluate its effectiveness on two real life grid data processing pipelines: NCSA image processing pipeline and WCER video processing pipeline. It enabled us to easily extract useful job and resource information and interpret them to make better scheduling decisions. Using it, we were able to understand failures better and were able to devise innovative methods to automatically avoid and recover from failures and dynamically adapt to grid environment improving fault-tolerance and performance.

Todays scientific applications have huge data requirements which continue to increase drastically every year. These data are generally accessed by many users from all across the the globe. This implies a major necessity to move huge amounts of data around wide area networks to complete the computation cycle, which brings with it the problem of efficient and reliable data placement. The current approach to solve this problem of data placement is either doing it manually, or employing simple scripts which do not have any automation or fault tolerance capabilities. Our goal is to make data placement activities first class citizens in the Grid just like the computational jobs. They will be queued, scheduled, monitored, managed, and even check-pointed. More importantly, it will be made sure that they complete successfully and without any human interaction. We also believe that data placement jobs should be treated differently from computational jobs, since they may have different semantics and different characteristics. For this purpose, we have developed Stork, a scheduler for data placement activities in the grid.

Different fields including biomedical-engineering, educational research and geology have an increasing need to process large amounts of video and make them electronically available at different locations. So far, this has been a failure-prone tedious operation with an operator needed to babysit the processing and off-site replication of processed video. In this work, we developed a fault-tolerant system that handles large scale processing and replication of digital video in a fully automated manner. The system is highly resilient and handles a variety of hardware, software and network failures making it possible to process videos using commodity clusters or grid resources. Finally, we discuss how the system is being used in educational research to process several hundred terabytes of video.

Grid computing presents two major challenges for deploying large scale applications across wide area networks gathering volunteers PC and clusters/parallel computers as computational resources: security and fault tolerance. This paper presents a lightweight Grid solution for the deployment of multi-parameters applications on a set of clusters protected by firewalls. The system uses a hierarchical design based on Condor for managing each cluster locally and XtremWeb for enabling resource sharing among the clusters. We discuss the security and fault tolerance mechanisms used for this design and demonstrate the usefulness of the approach measuring the performances of a multi-parameters bio-chemistry application deployed on two sites: University of Wisconsin/Madison and Paris South University. This experiment shows that we can efficiently and safely harness the computational power of about 200 PC distributed on two geographic sites.

This paper describes two systems to recover the Internet connectivity impaired by private networks and firewalls. These devices cause asymmetry in the Internet, making peer-to-peer computing difficult or even impossible. The Condor system is one of those that are severely impaired by the asymmetry. Compared to normal peer-to-peer computing applications, Condor has stricter requirements, which are representative to any grid computing. To make Condor seamlessly work across private networks and over firewalls, we designed and implemented Dynamic Port Forwarding (DPF) and Generic Connection Brokering (GCB). Both DPF and GCB satisfy the representative requirements. Furthermore DPF supports dedicated large clusters very well because it is simple, efficient, and highly scalable. On the other hand, GCB perfectly supports non-dedicated or personal clusters because it is independent to private network or firewall technologies and does not require airy administrative power to deploy it. In this paper, we describe the implementations of DPF and GCB and analyze them with respect to performance, deployability, security, and scalability.

Dynamic, heterogeneous and distributively owned resource environments present unique challenges to the problems of resource representation, allocation and management. Conventional resource management methods that rely on static models of resource allocation policy and behavior fail to address these challenges. We previously argued that Matchmaking provides an elegant and robust solution to resource management in such dynamic and federated environments. However, Matchmaking is limited by its purely bilateral formalism of matching a single customer with a single resource, precluding more advanced resource management services such as co-allocation. In this paper, we present Gangmatching, a multilateral extension to the Matchmaking model, and discuss the Gangmatching model and its associated implementation and performance issues in context of a real-world license management co-allocation problem.

We present a study of six batch-pipeline scientific workloads that are candidates for execution on computational grids. Whereas other studies focus on the behavior of single applications, this study characterizes workloads composed of pipelines of sequential processes that use file storage for communication and also share measurements of the memory, CPU, and I/O requirements of individual components as well as analyses of I/O sharing within complete batches. We conclude with a discussion of the ramifications of these workloads for end-to-end scalability and overall system design.

Despite many competitors, Ethernet became the dominant protocol for local area networking due to its simplicity, robustness, and efficiency in wide variety of conditions and technology. Reflecting on the current frailty of much software, grid and otherwise, we propose that the Ethernet approach to resource sharing is an effective and reliable technique for combining coarse-grained software when failures are common and poorly detailed. This approach involves placing several simple but important responsibilities on client software to acquire shared resources conservatively, to back off during periods of failure, and to inform competing clients when resources are in contention. We present a simple scripting language that simplifies and encourages the Ethernet approach, and demonstrate its use in several grid computing scenarios, including job submission, disk allocation, and data replication. We conclude with a discussion of the limitations of this approach, and describe how it is uniquely suited to high-level programming.

The drastic increase in the data requirements of scientific applications combined with an increasing trend towards collaborative research has resulted in the need to transfer large amounts of data among the participating sites. The general approach to transferring such large amounts of data has been to either dump data to tapes and mail them or employ scripts with an operator at each site to babysit the transfers to deal with failures. We introduce a framework which automates the whole process of data movement between different sites. The framework does not require any human intervention and it can recover automatically from various kinds of storage system, network, and software failures, guaranteeing completion of the transfers. The framework has sophisticated monitoring and tuning capability that increases the performance of the data transfers on the fly. The framework also generates on-the-fly visualization of the transfers making identification of problems and bottlenecks in the system simple.

Run-time tools are crucial to program development. In our desktop computer environments, we take for granted the availability of tools for operations such as debugging, profiling, tracing, checkpointing, and visualization. When programs move into distributed or Grid environments, it is difficult to find such tools. This difficulty is caused by the complex interactions necessary between application program, operating system and layers of job scheduling and process management software. As a result, each run-time tool must be individually ported to run under a particular job management system; for m tools and n environments, the problem becomes an m \times n effort, rather than the hoped-for m + n effort. Variations in underlying operating systems can make this problem even worse. The consequence of this situation is a paucity of tools in distributed and Grid computing environments. In response to the problem, we have analyzed a variety of job scheduling environments and run-time tools to better understand their interactions. From this analysis, we isolated what we believe are the essential interactions between the run-time tool, job scheduler and resource manager, and application program. We are proposing a standard interface, called the Tool Dæmon Protocol (TDP) that codifies these interactions and provides the necessary communication functions. We have implemented a pilot TDP library and experimented with Parador, a prototype using the Paradyn Parallel Performance tools profiling jobs running under the Condor batch-scheduling environment.

We present NeST a flexible software-only storage appliance designed to meet the storage needs of the Grid. NeST has three key features that make it well-suited for deployment in a Grid environment. First, NeST provides a generic data transfer architecture that supports multiple data transfer protocols (including GridFTP and NFS), and allows for the easy addition of new protocols. Second, NeST is dynamic, adapting itself on-the-fly so that it runs effectively on a wide range of hardware and software platforms. Third, NeST is Grid-aware, implying that features that are necessary for integration into the Grid, such as storage space guarantees, mechanisms for resource and data discovery, user authentication, and quality of service, are a part of the NeST infrastructure.

Error propagation is a central problem in grid computing. We re-learned this while adding a Java feature to the Condor computational grid. Our initial experience with the system was negative, due to the large number of new ways in which the system could fail. To reason about this problem, we developed a theory of error propagation. Central to our theory is the concept of an error's scope, defined as the portion of a system that it invalidates. With this theory in hand, we recognized that the expanded system did not properly consider the scope of errors it discovered. We modified the system according to our theory, and succeeded in making it a more robust platform for distributed computing.

Grid computing relies on fragile partnerships. Clients with hundreds or even thousands of pending service requests must seek out and form temporary alliances with remote servers eager to satisfy them. Yet, despite the high quality and reliability of these servers and their software, unexpected events and behavior are common. Communication networks, power systems, operating systems, middleware and operator intervention all conspire to attack even the most carefully arranged client-server interaction. To survive in such an imperfect world, customers of grid resources must be equipped with resilient client software that tolerates failures while aggressively representing their interests. Following our tradition of developing technology that harnesses the power of opportunistic resources, the Condor Project is actively engaged in developing the basic mechanisms for building dependable and effective grid computing clients. Guided by our experience and the practical needs of production users in disciplines as diverse as astronomy and sociology, the Project aims to equip users with powerful software that complements the reliability of the servers that they exploit. Our most visible product is the Condor-G job manager. Other research ventures, including the full Condor distributed system, offer valuable lessons in dependable client-side management. Dependability has been explored in a number of branches of computing, ranging from database systems to programming languages. The hard-earned lessons from these fields are also essential to grid computing. Fundamental concepts such as timeouts, logging, checkpoints, transactions, leases, and atomic operations must be employed and expressed in basic protocols and interfaces for CPU and I/O access. Without these techniques, clients and servers lose track of the other’s state, leading to missed opportunities, wasted resources, incorrect results, and unnecessary failures. This principle is espoused in systems such as Condor-G and protocols such as the most recent version of GRAM. In a Grid environment we must never view failure as a disaster. Rather, failures occur at every level and every interface, and must be expected and structured. No single failure must bring a computation to a halt, nor can any type of failure be retried indefinitely. Jobs may be retracted even from systems deemed reliable when better performance may be found elsewhere. In addition, we must always be careful to determine whether the source of a failure lies in the system or in the job itself. Examples of this principle are found in the DAGMan meta-scheduler and the fault-tolerant shell.

We investigate the scheduling problem that arises in parallel applications executing on a network of machines by using a mode of cycle-stealing. In this mode of execution a parallel application executes its tasks in several machines whenever they are idle. When the user reclaims the machine, tasks must relinquish control immediately. In this case, the parallel application has the risk of losing work in progress on reclaimed machines and, therefore, the total execution time of the parallel application will be affected by the need for rescheduling the pre-empted task. We first evaluate the impact on the performance of an application when it runs on two different scenarios: a set of N dedicated machines, and a set of N non-dedicated machines (in which pre-emption may occur). This study shows that losing machines may have a considerable impact on the execution time of the application and therefore, we propose and evaluate three simple strategies to alleviate this problem. All strategies are based on the use of additional machines, but they differ in the way that these extra machines are used. In the first strategy additional machines are added to the common pool of machines used by the application. The other two are based on task replication, in which the additional machines are used to execute certain tasks that are already running in other machines.

In recent years, there has been a dramatic increase in the amount of available computing and storage resources, yet few have been able to exploit these resources in an aggregated form. We present the Condor-G system, which leverages software from Globus and Condor to allow users to harness multi-domain resources as if they all belong to one personal domain. We describe the structure of Condor-G and how it handles job management, resource selection, security and fault tolerance.

The science of bioinformatics provides researchers with the tools necessary to unravel the mysteries of life and evolution, discover cures for disease, and control the evolution of living organisms. To assist researchers in managing the growing data processing and management demands associated with bioinformatics, we have created a production system that draws upon Grid based technologies to control several aspects of the process. We briefly discuss system architecture, results, and future directions of the project.

Access to remote data is one of the principal challenges of Grid computing. While performing I/O, Grid applications must be prepared for server crashes, performance variations and exhausted resources. To achieve high throughput in such a hostile environment, applications need a resilient service that moves data while hiding errors and latencies. We illustrate this idea with Kangaroo, a simple data movement system that makes opportunistic use of disks and networks to keep applications running. We demonstrate that Kangaroo can achieve better end-to-end performance than traditional data movement techniques, even though its individual components do not achieve high performance.

Grid applications have demanding I/O needs. Schedulers must bring jobs and data in close proximity in order to satisfy throughput, scalability, and policy requirements. Most systems accomplish this by making either jobs or data mobile. We propose a system that allows jobs and data to meet by binding execution and storage sites together into I/O communities which then participate in the wide-area system. The relationships between participants in a community may be expressed by the ClassAd framework. Extensions to the framework allow community members to express indirect relations. We demonstrate our implementation of I/O communities by improving the performance of a key high-energy physics simulation on an international distributed system.

Data-intensive applications in the Condor high-throughput computing (HTC) environment can place heavy demands on network resources for checkpointing and remote data access. We have developed mechanisms to monitor, control and schedule network usage in Condor. By managing network resources, these mechanisms provide administrative control over Condor's network usage and improve the execution efficiency of Condor applications.

Federated distributed systems present new challenges to resource management, which cannot be met by conventional systems that employ relatively static resource models and centralized allocators. We previously argued that matchmaking provides an elegant and robust resource management solution for these highly dynamic environments (R. Raman et al., 1998). Although powerful and flexible, multiparty policies (e.g., co-allocation) cannot be accommodated by matchmaking. The authors present Gang-Matching, a multilateral matchmaking formalism to address this deficiency.

Split execution is a common model for providing a friendly environment on a foreign machine. In this model, a remotely executing process sends some or all of its system calls back to a home environment for execution. Unfortunately, hand-coding split execution systems for experimentation and research is difficult and error-prone. We have built a tool, called Bypass, for quickly producing portable and correct split execution systems for unmodified legacy applications. We demonstrate Bypass by using it to transparently connect a POSIX application to a simple data staging system based on the Globus toolkit.

We describe the RD-OPT algorithm for DCT quantization optimization, which can be used as an efficient tool for near-optimal rate control in DCT-based compression techniques, such as JPEG and MPEG. RD-OPT measures DCT coefficient statistics for the given image data to construct rate/distortion-specific quantization tables with nearly optimal tradeoffs.

Process checkpointing is a basic mechanism required for providing high throughput computing service on distributively owned resources. We present a new process checkpoint and migration technique, called process hijacking, that uses dynamic program re-writing techniques to add checkpointing capability to a running program. Process hijacking makes it possible to checkpoint and migrate proprietary applications that cannot be re-linked with a checkpoint library, and it makes it possible to dynamically hand off an ordinary running process to a distributed resource management system such as Condor. We discuss the problems of adding checkpointing capability to a program already in execution: loading new code into the running process; and replacing functions of the process with calls to dynamically loaded functions. We use the DynInst API process editing library, augmented with a new call for replacing functions, to solve these problems.

This paper presents the CF-kernel method to estimate density functions from large datasets in a "best-efforts under the given resources" manner.By integrating the advantages of both the kernel method [WJ95] and the dynamical and incremental CF tree structure[ZRL96],

Organizations that offer external access to their data need a mechanism that ensures a desired level of service for local users. We propose such a mechanism, called the provider agent (PA) architecture, that protects local users by ensuring a (DBA specified) quality of service for local requests in the face of computational demands made by external requests. The PA is a general purpose solution that enhances most information systems currently available. The novelty of our approach is the combination of request profiling with load control mechanisms to improve both protection and performance, while not requiring any modifications to the underlying information system. We demonstrate the effectiveness of the proposed techniques with a prototype PA for a commercial DBMS.

Conventional resource management systems use a system model to describe resources and a centralized scheduler to control their allocation. We argue that this paradigm does not adapt well to distributed systems, particularly those built to support high throughput computing. Obstacles include heterogeneity of resources, which make uniform allocation algorithms difficult to formulate, and distributed ownership, leading to widely varying allocation policies. Faced with these problems, we developed and implemented the classified advertisement (classad) matchmaking framework, a flexible and general approach to resource management in distributed environment with decentralized ownership of resources. Novel aspects of the framework include a semi structured data model that combines schema, data, and query in a simple but powerful specification language, and a clean separation of the matching and claiming phases of resource allocation. The representation and protocols result in a robust, scalable and flexible framework that can evolve with changing resources. The framework was designed to solve real problems encountered in the deployment of Condor, a high throughput computing system developed at the University of Wisconsin-Madison. Condor is heavily used by scientists at numerous sites around the world. It derives much of its robustness and efficiency from the matchmaking architecture.

The recent dramatic improvements in the performance of commodity hardware has made clusters of workstations or PCs an attractive and economical platform upon which to build scalable database servers. These clusters have large aggregate memory capacities, however, since this global memory is distributed, good algorithms are necessary for memory management, or this large aggregate memory will go underutilized. The goal of the study is to develop and evaluate buffer management algorithms for database clusters. We propose a new buffer management algorithm, remote load sensitive caching (RLS caching), that uses novel techniques to combine data placement with a simple modification of standard client server page replacement algorithms to approximate a global LRU page replacement policy. Through an implementation in the SHORE database system, we evaluate the performance of RLS caching against other buffer management algorithms. Our study demonstrates that RLS caching indeed effectively manages the distributed memory of a server cluster.

In several working environments, production involves repeated executions of certain procedures. A workflow describes the individual tasks performed in these procedures and their interrelationships. Current workflow management systems (WFMSs) use a database management system (DBMS) to store task descriptions, and implement all workflow functionality in modules that run on top of the DBMS. Motivated by scientific workflows, we propose a much more DBMS-centric architecture, in which conventional database technology provides much of the desired scientific WFMS functionality. A key element of our approach is viewing the workflow as a web of data objects interconnected with active links that carry process descriptions. The workflow is fully defined as a database schema, and its execution is the gradual buildup of an instance of this schema through the active object links. For our work, we use the modeling and querying tools of Horse, the object-oriented DBMS that we have developed in the context of the Zoo Desktop Experiment Management Environment.

Despite the steady decrease in secondary storage prices, the data storage requirements of many organizations cannot be met economically using secondary storage alone. Tertiary storage offers a lower-cost alternative but is viewed as a second-class citizen in many systems. For instance, the typical solution in bringing tertiary-resident data under the control of a DBMS is to use operating system facilities to copy the data to secondary storage, and then to perform query optimization and execution as if the data had been in secondary storage all along. This approach fails to recognize the opportunities for saving execution time and storage space if the data were accessed directly on tertiary devices and in parallel with other I/Os. We explore how to join two DBMS relations stored on magnetic tapes. Both relations are assumed to be larger than available disk space. We show how Grace Hash Join can be modified to handle a range of tape relation sizes. The modified algorithms access data directly on tapes and exploit parallelism between disk and tape I/Os. We also provide performance results of an experimental implementation of the algorithms.

Popular Web sites are already experiencing very heavy loads, and these loads will only increase as the number of users accessing them grows. These loads create both CPU and I/O bottlenecks. One promising solution already being employed to eliminate the CPU bottleneck is to replace a single processor server with a cluster of servers. Our goal in this paper is to develop buffer management algorithms that exploit the aggregate memory capacity of the machines in such a server cluster to attack the I/O bottleneck. The key challenge in designing such buffer management algorithms turns out to be controlling data replication so as to achieve a good balance between intra-cluster network traffic and disk I/O. At one extreme, the straightforward application of client-server memory management techniques to this cluster architecture causes duplication in memory among the servers and this tends to reduce network traffic but increases disk I/O, whereas at the other extreme, eliminating all duplicates tends to increase network traffic while reducing disk I/O. Accordingly, we present a new algorithm, called Hybrid, that dynamically controls the amount of duplication. Through a detailed simulation, we show that, on workloads that are characteristic of those experienced by Web servers, the Hybrid algorithm correctly trades off intra-cluster network traffic and disk I/O to minimize average response time.

DIAS

DEVise is a data exploration system that allows users to easily develop, browse, and share visual presentation of large tabular datasets (possibly containing or referencing multimedia objects) from several sources. The DEVise framework is being implemented in a tool that has been already successfully applied to a variety of real applications by a number of user groups.

DEVise is a data exploration system that allows users to easily develop, browse, and share visual presentations of large tabular datasets (possibly containing or referencing multimedia objects) from several sources. The DEVise framework, implemented in a tool that has been already successfully applied to a variety of real applications by a number of user groups, makes several contributions. In particular, it combines support for extended relational queries with powerful data visualization features. Datasets much larger than available main memory can be handled—DEVise is currently being used to visualize datasets well in excess of 100MB—and data can be interactively examined at several levels of detail: all the way from meta-data summarizing the entire dataset, to large subsets of the actual data, to individual data records. Combining querying (in general, data processing) with visualizations gives us a very versatile tool, and presents several novel challenges.

We have studied the needs of a wide range of experimental disciplines, developed solutions to some of the basic problems in experiment management and made significant progress towards implementing a simple desktop experiment management environment (DEME) called Zoo. Our work has proceeded in a tight loop between developing generic experiment management technology that is implemented in a generic tool, installing customized enhancements of the tool that constitute full systems [complete customized desktop experiment management systems (CDEMSs)] in laboratories of interest, and using the provided feedback to guide our research directions. In this paper, we first outline the overall architecture of Zoo and then discuss a particular experiment.

Client-server database systems based on a data shipping model can exploit client memory resources by caching copies of data items across transaction boundaries. Caching reduces the need to obtain data from servers or other sites on the network. In order to ensure that such caching does not result in the violation of transaction semantics, a transactional cache consistency maintenance algorithm is required. Many such algorithms have been proposed in the literature and, as all provide the same functionality, performance is a primary concern in choosing among them. In this article we present a taxonomy that describes the design space for transactional cache consistency maintenance algorithms and show how proposed algorithms relate to one another. We then investigate the performance of six of these algorithms, and use these results to examine the tradeoffs inherent in the design choices identified in the taxonomy. The results show that the interactions among dimensions of the design space impact performance in many ways, and that classifications of algorithms as simply “pessimistic” or “optimistic” do not accurately characterize the similarities and differences among the many possible cache consistency algorithms.

In this paper, the RD-OPT algorithm for optimizing discrete cosine transform quantization tables [Ratnakar and Livny, 1995] is extended to incorporate global thresholding. Performance gains are possible by zeroing off some DCT coefficients in DCT-based image compression. We describe a global thresholding scheme, in which the zeroing thresholds for coefficients can be arbitrarily different from those determined by the quantization table. Unlike local thresholding [Crouse and Ramchandran, 1995], the zeroing decisions are not made separately for each image block. This simplifies the use of thresholding, is easier to optimize and is almost as effective as local thresholding.

We present the Distributed Batch Controller (DBC), a system built to support batch processing of large scientific datasets. The DBC implements a federation of autonomous workstation pools, which may be widely distributed. Individual batch jobs are executed using idle workstations in these pools. Input data are staged to the pool before processing begins. We describe the architecture and implementation of the DBC, and present the results of experiments in which it is used to perform image compression.

In this paper we revisit the problem of achieving multi-class workload response time goals by automatically adjusting the buffer memory allocations of each workload class. We discuss the virtues and limitations of previous work with respect to a set of criteria we lay out for judging the success of any goal-oriented resource allocation algorithm. We then introduce the concept of hit rate concavity and develop a new goal-oriented buffer allocation algorithm, called Class Fencing, that is based on this concept. Exploiting the notion of hit rate concavity results in an algorithm that not only is as accurate and stable as our previous work, but also more responsive, more robust, and simpler to implement.

Finding useful patterns in large datasets has attracted considerable interest recently, and one of the most widely studied problems in this area is the identification of clusters, or densely populated regions, in a multi-dimensional dataset. Prior work does not adequately address the problem of large datasets and minimization of I/O costs.This paper presents a data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), and demonstrates that it is especially suitable for very large databases. BIRCH incrementally and dynamically clusters incoming multi-dimensional metric data points to try to produce the best quality clustering with the available resources (i.e., available memory and time constraints). BIRCH can typically find a good clustering with a single scan of the data, and improve the quality further with a few additional scans. BIRCH is also the first clustering algorithm proposed in the database area to handle "noise" (data points that are not part of the underlying pattern) effectively.We evaluate BIRCH's time/space efficiency, data input order sensitivity, and clustering quality through several experiments. We also present a performance comparisons of BIRCH versus CLARANS, a clustering method proposed recently for large datasets, and show that BIRCH is consistently superior.

The problem of translating database objects into a flat format to be written out in a flat Ascii file or, conversely, translating the contents of a file into a complex database object arises in several applications. It is especially important in scientific database applications, where file-based communication with external programs (e.g., visualization packages or model simulations) is very common. We introduce Frog, a visual tool that can be used to specify translations between database objects and flat files, requiring no programming by the user. The tool can deal with objects of arbitrary complexity, without the object complexity being directly reflected in the complexity of the corresponding visual interaction. Based on the visual actions of the user, the tool stores enough information in a map-file, whose contents are used at run-time by another tool, Turtle, to translate any chosen database object into the appropriate file layout. The tool has been developed as part of the ZOO desktop experiment management environment and has been used by a few experimental scientists with success.

The Discrete Cosine Transform (DCT) is widely used in lossy image and video compression schemes such as JPEG and MPEG. In this paper we describe RD-OPT, an efficient algorithm for constructing DCT quantization tables with optimal rate-distortion tradeoffs for a given image. The algorithm uses DCT coefficient distribution statistics in a novel way and uses a dynamic programming strategy to produce optimal quantization tables over a wide range of rates and distortions. It can be used to compress images at any desired signal-to-noise ratio or compressed size.

This paper presents the SEQ model which is the basis for a system to manage various kinds of sequence data. The model separates the data from the ordering information, and includes operators based on two distinct abstractions of a sequence. The main contributions of the SEQ model are: (a) it can deal with different types of sequence data, (b) it supports an expressive range of sequence queries, (c) it draws from many of the diverse existing approaches to modeling sequence data.>

We demonstrate the close relationship between data placement and memory management for symmetric multi-server OODBMS. We propose and investigate memory management algorithms for two data placement strategies, namely declustering and clustering. Through a detailed simulation, we show that by declustering the data most of the benefits of complex global memory management algorithms are realized by simple algorithms. In contrast we show that when data is clustered, the simple algorithms perform poorly.>

Today large amounts of data are stored on tertiary storage media such as magnetic tapes and optical disks. DBMSs typically operate only on magnetic disks since they know how to maneuver disks and how to optimize accesses on them. Tertiary devices present a problem for DBMSs since these devices have dismountable media and have very different operational characteristics compared to magnetic disks. For instance, most tape drives offer very high capacity at low cost but are accessed sequentially, involve lengthy latencies, and deliver lower bandwidth. Typically, the scope of a DBMS's query optimizer does not include tertiary devices, and the DBMS might not even know how to control and operate upon tertiary-resident data. In a three-level hierarchy of storage devices (main memory, disk, tape), the typical solution is to elevate tape-resident data to disk devices, thus bringing such data into the DBMS' control, and then to perform the required operations on disk. This requires additional space on disk and may not give the lowest response time possible. With this challenge in mind, we studied the trade-offs between memory and disk requirements and the execution time of a join with the help of two well-known join methods. The conventional, disk-based Nested Block Join and Hybrid Hash Join were modified to operate directly on tapes. An experimental implementation of the modified algorithms gave us more insight into how the algorithms perform in practice. Our performance analysis shows that a DBMS desiring to operate on tertiary storage will benefit from special algorithms that operate directly on tape-resident data and take into account and exploit the mismatch in disk and tape characteristics.

In recent years, a demand for real-time systems that can manipulate large amounts of shared data has led to the emergence of real-time database systems (RTDBS) as a research area. This paper focuses on the problem of scheduling queries in RTDBSs. We introduce and evaluate a new algorithm called Priority Adaptation Query Resource Scheduling (PAQRS) for handling both single class and multiclass query workloads. The performance objective of the algorithm is to minimize the number of missed deadlines, while at the same time ensuring that any deadline misses are scattered across the different classes according to an administratively-defined miss distribution. This objective is achieved by dynamically adapting the system's admission, memory allocation, and priority assignment policies according to its current resource configuration and workload characteristics. A series of experiments confirms that PAQRS is very effective for real-time query scheduling.>

The demanding performance objectives that real-time database systems (RTDBS) face necessitate the use of priority resource scheduling. This paper introduces a Priority Memory Management (PMM) algorithm that is designed to schedule queries in RTDBS. PMM attempts to minimize the number of missed deadlines by adapting both its multiprogramming level and its memory allocation strategy to the characteristics of the offered workload. A series of simulation experiments confirms that PMM's admission control and memory allocation mechanisms are very effective for real-time query scheduling.

Many applications require the ability to manipulate sequences of data. We motivate the importance of sequence query processing, and present a framework for the optimization of sequence queries based on several novel techniques. These include query transformations, optimizations that utilize meta-data, and caching of intermediate results. We present a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates. This work also identifies a number of directions in which future research can be directed.

Article Free Access Share on Tapes hold data, too: challenges of tuples on tertiary store Authors: Michael J. Carey Computer Science Dept., University of Wisconsin, Madison, WI Computer Science Dept., University of Wisconsin, Madison, WIView Profile , Laura M. Haas IBM Almaden Research Center, K55/801, San Jose, CA IBM Almaden Research Center, K55/801, San Jose, CAView Profile , Miron Livny Computer Science Dept., University of Wisconsin, Madison, WI Computer Science Dept., University of Wisconsin, Madison, WIView Profile Authors Info & Claims SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of dataJune 1993Pages 413–417https://doi.org/10.1145/170035.170103Published:01 June 1993Publication History 30citation211DownloadsMetricsTotal Citations30Total Downloads211Last 12 Months55Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

With the advent of real-time and goal-oriented database systems, priority scheduling is likely to be an important feature in future database management systems. A consequence of priority scheduling is that a transaction may lose its buffers to higher-priority transactions, and may be given additional memory when transactions leave the system. Due to their heavy reliance on main memory, hash joins are especially vulnerable to fluctuations in memory availability. Previous studies have proposed modifications to the hash join algorithm to cope with these fluctuations, but the proposed algorithms have not been extensively evaluated or compared with each other. This paper contains a performance study of these algorithms. In addition, we introduce a family of memory-adaptive hash join algorithms that turns out to offer even better solutions to the memory fluctuation problem that hash joins experience.

The issue of priority assignment is addressed, in firm multiclass real-time database systems (RTDBSs) where classes are distinguished by their mean sizes. It is shown that the earliest deadline scheduling principle, upon which a number of existing priority assignment policies are based, discriminates significantly against longer transactions. This observation has motivated the development of a novel dynamic priority assignment scheme that improves the chances for long transactions to meet their time constraints, thereby providing a fairer mechanism for use in multiclass RTDBS transaction scheduling.>

In this paper, we identify some of the fundamental issues that must be addressed in designing a desktop Experiment Management System (EMS). We develop an abstraction of the set of activities performed by scientists throughout the course of an experimental study, and based on that abstraction we propose an EMS architecture that can support all such activities. The proposed EMS architecture is centered around the extensive use of conceptual schemas, which express the structure of information in experimental studies. Schemas are called to play new roles that are not usually found in traditional database systems. We provide a detailed exposition of these new roles and describe certain characteristics that the data model of the EMS must have in order for schemas expressed in it to successfully play these roles. Finally, we present the specifics of our own effort to develop an EMS, focusing on the main features of the data model of the system, which we have developed based on the needs of experiment management.

A token ring local area network, the parallelring, is introduced. The ability to concurrently support multiple communication paths on a single loop in an efficient and fair manner differentiates the parallelring from earlier ring architectures. This is accomplished by using a message destination removal scheme and, hence, allowing more than one station to transmit a variable-length frame at a time. Simulation studies show that the parallelring exhibits better performance in terms of throughput-delay characteristics than the other token rings. In addition, a priority scheme is used in the parallelring to provide messages of different time constraints with different media access priorities so that it can support media access fairness and real-time services. In the parallelring, error detection and recovery are completely decentralized.>

A new priority assignment algorithm called adaptive earliest deadline (AED) is given that stabilizes the overload performance of the earliest deadline policy in a real-time database system (RTDBS) environment. The AED algorithm uses a feedback control mechanism to achieve this objective and does not require knowledge of transaction characteristics. Using a detailed simulation model, the authors compare the performance of AED with respect to earliest deadline and other fixed priority schemes. They also present and evaluate an extension of the AED algorithm called hierarchical earliest deadline (HED), which is designed to handle applications that assign different values to transactions and where the goal is to maximize the total value of the in-time transactions.>

article Free Access Share on Data caching tradeoffs in client-server DBMS architectures Authors: Michael J. Carey Computer Sciences Department, University of Wisconsin-Madison Computer Sciences Department, University of Wisconsin-MadisonView Profile , Michael J. Franklin Computer Sciences Department, University of Wisconsin-Madison Computer Sciences Department, University of Wisconsin-MadisonView Profile , Miron Livny Computer Sciences Department, University of Wisconsin-Madison Computer Sciences Department, University of Wisconsin-MadisonView Profile , Eugene J. Shekita IBM Almaden Research Center and Computer Sciences Department, University of Wisconsin-Madison IBM Almaden Research Center and Computer Sciences Department, University of Wisconsin-MadisonView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 357–366https://doi.org/10.1145/119995.115854Published:01 April 1991Publication History 151citation1,074DownloadsMetricsTotal Citations151Total Downloads1,074Last 12 Months100Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A performance model designed for studying active DBMS performance issues is described. The authors present the results of simulation experiments in which system performance was studied as a function of transaction boundary semantics for varying levels of data contention, rule complexity, and data sharing between externally submitted tasks and rule management tasks. The results demonstrate that the way in which transaction boundaries are imposed can have a major impact on the performance of an active DBMS. It is therefore concluded that this aspect of rule semantics must be carefully considered at the time that rules are specified.>

data replicationand "distributedness" of accesses to replicated data.The results provide some interesting insights into how the trade-offs between early and late conflict detection vary as a function of message cost, and should prove useful to distributed database system designers.

A number of concurrency control performance studies have shown that, under high levels of data contention, concurrency control algorithms can exhibit thrashing behavior which is detrimental to overall system performance. In this paper, we present an approach to eliminating thrashing in the case of two-phase locking, a widely used concurrency control algorithm. Our solution, which we call the 'Half-and-Half' Algorithm, involves monitoring the state of the DBMS in order to dynamically control the multiprogramming level of the system. Results from a performance study indicate that the Half-and-Half algorithm can be very effective at preventing thrashing under a wide range of operating conditions and workloads.

Performance studies of concurrency control algorithms for conventional database systems have shown that, under most operating circumstances, locking protocols outperform optimistic techniques. Real-time database systems have special characteristics - timing constraints are associated with transactions, performance criteria are based on satisfaction of these timing constraints, and scheduling algorithms are priority driven. In light of these special characteristics, results regarding the performance of concurrency control algorithms need to be re-evaluated. We show in this paper that the following parameters of the real-time database system - its policy for dealing with transactions whose constraints are not met, its knowledge of transaction resource requirements, and the availability of resources - have a significant impact on the relative performance of the concurrency control algorithms. In particular, we demonstrate that under a policy that discards transactions whose constraints are not met, optimistic concurrency control outperforms locking over a wide range of system utilization. We also outline why, for a variety of reasons, optimistic algorithms appear well-suited to real-time database systems.

The authors (1990) have shown that in real-time database systems that discard late transactions, optimistic concurrency control outperforms locking. Although the optimistic algorithm used in that study, OPT-BC, did not factor in transaction deadlines in making data conflict resolution decisions, it still outperformed a deadline-cognizant locking algorithm. A discussion is presented of why adding deadline information to optimistic algorithms is a nontrivial problem, and some alternative methods of doing so are described. A new real-time optimistic concurrency control algorithm, WAIT-50, is presented that monitors transaction conflict states and gives precedence to urgent transactions in a controlled manner. WAIT-50 is shown to provide significant performance gains over OPT-BC under a variety of operating conditions and workloads.>

Results obtained in a study of algorithms to implement a distributed-shared memory in a distributed (loosely coupled) environment are described. Distributed-shared memory is the implementation of shared memory across multiple nodes in a distributed system. This is accomplished using only the private memories of the nodes by controlling access to the pages of the shared memory and transferring data to and from the private memories when necessary. Alternative algorithms are analyzed to implement distributed-shared memory. The algorithms are analyzed and compared over a wide range of conditions. Application characteristics are identified which can be exploited by the algorithms. The conditions under which the algorithms analyzed perform better or worse than the other alternatives are shown. Results are obtained via simulation using a synthetic reference generator.>

While several distributed (or 'shared nothing') database machines exist in the form of prototypes or commercial products, and a number of distributed concurrency control algorithms are available, the effect of parallelism on concurrency control performance has received little attention. This paper examines the interplay between parallelism and transaction performance in a distributed database machine context. Four alternative concurrency control algorithms are considered, including two-phase locking, wound-wait, basic timestamp ordering, and optimistic concurrency control. Issues addressed include how performance scales as a function of machine size and the degree to which partitioning the database for intra-transaction parallelism improves performance for the different algorithms. We examine performance from several perspectives, including response time, throughput, and speedup, and we do so over a fairly wide range of system loads. We also examine the performance impact of certain important overhead factors (e.g., communication and process initiation costs) on the four alternative concurrency control algorithms.

The authors consider whether the addition of a migration facility to a distributed scheduler already capable of placement can significantly improve performance. They examine performance over a broad range of workload characteristics and file system structures. They find that while placement alone is capable of large improvement in performance, the addition of migration can achieve considerable additional improvement.>

The design, implementation, and performance of the Condor scheduling system, which operates in a workstation environment, are presented. The system aims to maximize the utilization of workstations with as little interference as possible between the jobs it schedules and the activities of the people who own workstations. It identifies idle workstations and schedules background jobs on them. When the owner of a workstation resumes activity at a station, Condor checkpoints the remote job running on the station and transfers it to another workstation. The system guarantees that the job will eventually complete, and that very little, if any, work will be performed more than once. A performance profile of the system is presented that is based on data accumulated from 23 stations during one month.>

As the size and complexity of processing and manufacturing systems increases, the need for Database Management Systems (DBMS) that meet the special needs of studies that experiment with such systems becomes more current. System analysts who study the performance of modern processing systems have to manipulate large amounts of data in order to profile the behavior of the system. They have to identify the relationship between the properties of a compound system and a wide spectrum of performance metrics. In a recent study in which we have analyzed a set of distributed concurrency control algorithms, we performed more than 1400 simulation experiments. Each experiment was characterized by more than 6000 input parameters and generated more than 400 output values. It is thus clear that powerful means for defining the structure and properties of complex systems are needed, as well as efficient tools to retrieve the data accumulated in the course of the study. We are currently engaged in an effort to develop and implement the DELAB simulation laboratory that aims to provide such means and tools for simulation studies.

We investigate two schemes for placing data on multiple disks. We show that declustering (spreading each file across several disks) is inherently better than clustering (placing each file on a single disk) due to a number of reasons including parallelism and uniform load on all disks.

A number of recent studies have examined the performance of concurrency control algorithms for database management systems. The results reported to date, rather than being definitive, have tended to be contradictory. In this paper, rather than presenting “yet another algorithm performance study,” we critically investigate the assumptions made in the models used in past studies and their implications. We employ a fairly complete model of a database environment for studying the relative performance of three different approaches to the concurrency control problem under a variety of modeling assumptions. The three approaches studied represent different extremes in how transaction conflicts are dealt with, and the assumptions addressed pertain to the nature of the database system's resources, how transaction restarts are modeled, and the amount of information available to the concurrency control algorithm about transactions' reference strings. We show that differences in the underlying assumptions explain the seemingly contradictory performance results. We also address the question of how realistic the various assumptions are for actual database systems.

Article Free Access Share on Models for studying concurrency control performance: alternatives and implications Authors: Rakesh Agrawal AT&T Bell Laboratories, Murray Hill NJ AT&T Bell Laboratories, Murray Hill NJView Profile , Michael J. Carey Computer Sciences Department, University of Wisconsin, Madison WI Computer Sciences Department, University of Wisconsin, Madison WIView Profile , Miron Livny Computer Sciences Department, University of Wisconsin, Madison WI Computer Sciences Department, University of Wisconsin, Madison WIView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 108–121https://doi.org/10.1145/318898.318909Published:01 May 1985Publication History 63citation638DownloadsMetricsTotal Citations63Total Downloads638Last 12 Months46Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An extension to the token ring protocol which allows a special type of arithmetic, called shift arithmetic, to be performed directly on the node's interfaces is proposed. The new protocol is based on an approach in which the communication channel and the interfaces form an environment in which simple commands can be executed. Each command operates on operands located at the interfaces, and places the result at the interface which initiated the command. The commands utilize the mandatory 1-bit delay of the token ring protocol to implement arithmetic and logical operations on the operands without further delay. The goal of this protocol is to enhance the performance of distributed algorithms on ring networks by performing many simple tasks in the lowest possible level. The authors show that this protocol is especially useful for load sharing in local area networks. Other potential application areas include parallel algorithms, distributed simulation, distributed operating systems, distributed databases and real-time computations.

Three different load balancing algorithms for distributed systems that consist of a number of identical processors and a CSMA communication system are presented in this paper. Some of the properties of a multi-resource system and the balancing process are demonstrated by an analytic model. Simulation is used as a mean for studying the interdependency between the parameters of the distributed system and the behaviour of the balancing algorithm. The results of this study shed light on the characteristics of the load balancing process.