Abstract “Volunteer computing” is the use of consumer digital devices for high-throughput scientific computing. It can provide large computing capacity at low cost, but presents challenges due to device heterogeneity, unreliability, and churn. BOINC, a widely-used open-source middleware system for volunteer computing, addresses these challenges. We describe BOINC’s features, architecture, implementation, and algorithms.

Volunteer computing systems are large-scale distributed systems with large number of heterogeneous and unreliable Internet-connected hosts. Volunteer computing resources are suitable mainly to run High-Throughput Computing (HTC) applications due to their unavailability rate and frequent churn. Although they provide Peta-scale computing power for many scientific projects across the globe, efficient usage of this platform for different types of applications still has not been investigated in depth. So, characterizing, analyzing and modeling such resources availability in volunteer computing is becoming essential and important for efficient application scheduling. In this paper, we focus on statistical modeling of volunteer resources, which exhibit non-random pattern in their availability time. The proposed models take into account the autocorrelation structure in subset of hosts whose availability has short/long-range dependence. We apply our methodology on real traces from the SETI@home project with more than 230,000 hosts. We show that Markovian arrival process can model the availability and unavailability intervals of volunteer resources with a reasonable to excellent level of accuracy.

Understanding and modeling resources of Internet end hosts are essential for the design of desktop software and Internet-distributed applications. In this paper, we develop a correlated resource model of Internet end hosts based on real-trace data taken from several volunteer computing projects, including SETI@home. This data cover a five-year period with statistics for 6.7 million hosts. Our resource model is based on statistical analysis of host computational power, memory, and storage as well as how these resources change over time and the correlations among them. We find that resources with few discrete values (core count, memory) are well modeled by approximations governing the change of relative resource quantities over time. Resources with a continuous range of values are well modeled by correlated log-normal distributions (cache, processor speed, and available disk space). We validate and show the utility of the model by applying it to a resource allocation problem for Internet-distributed applications, and compare it to other models. We also make our trace data and tool for automatically generating realistic Internet end hosts publicly available.

Many large-scale distributed computing applications demand real-time responses by soft deadlines. To enable such real-time task distribution and execution on the volunteer resources, we previously proposed the design of the real-time volunteer computing platform called RT-BOINC. The system gives low O(1) worst-case execution time for task management operations, such as task scheduling, state transitioning, and validation. In this work, we present a full implementation RT-BOINC, adding new features including deadline timer and parameter-based admission control. We evaluate RT-BOINC at large scale using two real-time applications, namely, the games Go and Chess. The results of our case study show that RT-BOINC provides much better performance than the original BOINC in terms of average and worst-case response time, scalability and efficiency.

Understanding and modelling resources of Internet end hosts is essential for the design of desktop software and Internet-distributed applications. In this paper we develop a correlated resource model of Internet end hosts based on real trace data taken from the SETI@home project. This data covers a 5-year period with statistics for 2.7 million hosts. The resource model is based on statistical analysis of host computational power, memory, and storage as well as how these resources change over time and the correlations between them. We find that resources with few discrete values (core count, memory) are well modeled by exponential laws governing the change of relative resource quantities over time. Resources with a continuous range of values are well modeled with either correlated normal distributions (processor speed for integer operations and floating point operations) or log-normal distributions (available disk space). We validate and show the utility of the models by applying them to a resource allocation problem for Internet-distributed applications, and demonstrate their value over other models. We also make our trace data and tool for automatically generating realistic Internet end hosts publicly available.

International audience

Computational science is placing new demands on optimization algorithms as the size of data sets and the computational complexity of scientific models continue to increase. As these complex models have many local minima, evolutionary algorithms (EAs) are very useful for quickly finding optimal solutions in these challenging search spaces. In addition to the complex search spaces involved, calculating the objective function can be extremely demanding computationally. Because of this, distributed computation is a necessity. In order to address these computational demands, top-end distributed computing systems are surpassing hundreds of thousands of computing hosts; and as in the case of Internet based volunteer computing systems, they can also be highly heterogeneous and faulty. This work examines asynchronous strategies for distributed EAs using simulated computing environments. Results show that asynchronous EAs can scale to hundreds of thousands of computing hosts while being highly resilient to heterogeneous and faulty computing environments, something not possible for traditional distributed EAs which require synchronization. While the simulation not only provides insight as to how asynchronous EAs perform on distributed computing environments with different latencies and heterogeneity, it also serves as a sanity check because live distributed systems require problems with high computation to communication ratios and traditional benchmark problems cannot be used for meaningful analysis due to their short computation times.

Popular web services and applications such as Google Apps, DropBox, and Go.Pc introduce a wasteful imbalance of processing resources. Each host operated by a provider serves hundreds to thousands of users, treating their PCs as thin clients. Tapping the processing, storage and networking capacities of these non-dedicated resources promises to reduce the size of required hardware basis significantly. Consequently, it presents a noteworthy opportunity for service providers and operators of cloud computing infrastructures. We investigate how a mixture of dedicated (and so highly available) hosts and non-dedicated (and so highly volatile) hosts can be used to provision a processing tier of a large-scale web service. We discuss an operational model which guarantees long-term availability despite of host churn, and study multiple aspects necessary to implement it. These include: ranking of non-dedicated hosts according to their long-term availability behavior, short-term availability modeling of these hosts, and simulation of migration and group availability levels using real-world availability data from 10,000 non-dedicated hosts. We also study the tradeoff between a larger share of dedicated hosts vs. higher migration rate in terms of costs and SLA objectives. This yields an optimization approach where a service provider can find a suitable balance between costs and service quality. The experimental results show that it is possible to achieve a wide spectrum of such modes, ranging from 3.6 USD/hour to 5 USD/hour for a group of at least 50 hosts available with probability greater than 0.90.

BOINC is a platform for volunteer computing. The server component of BOINC embodies a number of scheduling policies and parameters that have a large impact on the projects throughput and other performance metrics. We have developed a system, EmBOINC, for studying these policies and parameters. EmBOINC uses a hybrid approach: it simulates a population of volunteered clients (including heterogeneity, churn, availability, reliability) and it emulates the server component; that is, it uses the actual server software and its associated database. This paper describes the design of EmBOINC and validates its results based on trace data from an existing BOINC project.

Cloud Computing has taken commercial computing by storm. However, adoption of cloud computing platforms and services by the scientific community is in its infancy as the performance and monetary cost-benefits for scientific applications are not perfectly clear. This is especially true for desktop grids (aka volunteer computing) applications. We compare and contrast the performance and monetary cost-benefits of clouds for desktop grid applications, ranging in computational size and storage. We address the following questions: (i) What are the performance tradeoffs in using one platform over the other? (ii) What are the specific resource requirements and monetary costs of creating and deploying applications on each platform? (iii) In light of those monetary and performance cost-benefits, how do these platforms compare? (iv) Can cloud computing platforms be used in combination with desktop grids to improve cost-effectiveness even further? We examine those questions using performance measurements and monetary expenses of real desktop grids and the Amazon elastic compute cloud.

In the age of cloud, Grid, P2P, and volunteer distributed computing, large-scale systems with tens of thousands of unreliable hosts are increasingly common. Invariably, these systems are composed of heterogeneous hosts whose individual availability often exhibit different statistical properties (for example stationary versus non-stationary behavior) and fit different models (for example Exponential, Weibull, or Pareto probability distributions). In this paper, we describe an effective method for discovering subsets of hosts whose availability have similar statistical properties and can be modelled with similar probability distributions. We apply this method with about 230,000 host availability traces obtained from a real large-scale Internet-distributed system, namely SETI@home. We find that about 34% of hosts exhibit availability that is a truly random process, and that these hosts can often be modelled accurately with a few distinct distributions from different families. We believe that this characterization is fundamental in the design of stochastic scheduling algorithms across large-scale systems where host availability is uncertain.

Middleware systems for volunteer computing convert a set of computers that is large and diverse (in terms of hardware, software, availability, reliability, and trustworthiness) into a unified computing resource. This involves a number of scheduling policies and parameters, which have a large impact on the throughput and other performance metrics. How can we study and refine these policies? Experimentation in the context of a working project is problematic, and it is difficult to accurately model complex middleware in a conventional simulator. Instead, we use an approach in which the policies being studied are “emulated”, using parts of the actual middleware. In this paper we describe EmBOINC, an emulator based on the BOINC middleware system. EmBOINC simulates a population of volunteered clients (including heterogeneity, churn, availability, and reliability) and emulates the BOINC server components. After describing the design of EmBOINC and its validation, we present three case studies in which the impact of different scheduling policies are quantified in terms of throughput, latency, and starvation metrics.

Internet based volunteer computing projects such as SETI@home are currently restricted to performing coarse grained, embarrassingly parallel master-worker style tasks. This is partly due to the “pull” nature of task distribution in volunteer computing environments, where workers request tasks from the master rather than the master assigning tasks to arbitrary workers. In this paper we propose algorithms for computing batches of medium grained tasks with deadlines in pull-style volunteer computing environments. We develop models of unreliable workers based on analysis of trace data from an actual volunteer computing project. These models are used to develop algorithms for task distribution in volunteer computing systems with a high probability of meeting batch deadlines. We develop algorithms for perfectly reliable workers, computation-reliable workers and unreliable workers. Finally, we demonstrate the effectiveness of the algorithms through simulations using traces from actual volunteer computing environments.

BOINC, a middleware system for volunteer computing, allows hosts to be attached to multiple projects. Each host periodically requests jobs from project servers and executes the jobs. This process involves three interrelated policies: 1) of the runnable jobs on a host, which to execute? 2) when and from what project should a host request more work? 3) what jobs should a server send in response to a given request? 4) How to estimate the remaining runtime of a job? In this paper, we consider several alternatives for each of these policies. Using simulation, we study various combinations of policies, comparing them on the basis of several performance metrics and over a range of parameters such as job length variability, deadline slack, and number of attached projects.

BOINC, a middleware system for volunteer computing, involves projects, which distribute jobs, and hosts, which execute jobs. The local (host-level) scheduler addresses two issues: when to fetch new jobs from a project and, of the currently runnable jobs, which to execute. It seeks to simultaneously satisfy a number of constraints - such as maintaining given long-term ratios of work between projects, meeting deadlines for job reporting, and providing variety to the volunteer - using uncertain, dynamic information about resources and jobs. We describe these goals and factors, and discuss BOINC's local scheduling policies.

"Volunteer computing" uses Internet-connected computers, volunteered by their owners, as a source of computing power and storage. This paper studies the potential capacity of volunteer computing. We analyzed measurements of over 330,000 hosts participating in a volunteer computing project. These measurements include processing power, memory, disk space, network throughput, host availability, userspecified limits on resource usage, and host churn. We show that volunteer computing can support applications that are significantly more data-intensive, or have larger memory and storage requirements, than those in current projects.

Several scientific projects use BOINC (Berkeley Open Infrastructure for Network Computing) to perform largescale simulations using volunteers' computers (workers) across the Internet. In general, the scheduling of tasks in BOINC uses a First-Come-First-Serve policy and no attention is paid to workers' past performance, such as whether or not they have tended to perform tasks promptly and correctly. In this paper we use SimBA, a discrete-event Simulator of BOINC Applications, to study new threshold-based scheduling strategies for BOINC projects that use availability and reliability metrics to classify workers and distribute tasks according to this classification. We show that if availability and reliability thresholds are selected properly, then the workers' throughput of valid results increases significantly in BOINC projects.

Volunteer computing is a form of distributed computing in which the general public volunteers processing and storage to scientific research projects. BOINC, a middleware system for volunteer computing, is currently used by about 20 projects, to which 300,000 volunteers and 450,000 computers supply 350 TeraFLOPS of processing power. A BOINC client program runs on the volunteered hosts and manages the execution of applications. Together with a library linked to applications, it implements a runtime system providing process management, graphics control, checkpointing, file access, and other functions. This runtime system must handle widely varying applications, must provide features and properties desired by volunteers, and must work on many platforms. This paper describes the problems in designing a runtime system having these properties, and how these problems are solved in BOINC.

Volunteer computing projects use a task server to manage work. Clients periodically communicate with the server to report completed tasks and get new tasks. The rate at which the server can dispatch tasks may limit the computing power available to the project. This paper discusses the design of the task server in BOINC, a middleware system for volunteer computing. We present measurements of the CPU time and disk I/O used by a BOINC server, and show that a server consisting of a single inexpensive computer can distribute on the order of 8.8 million tasks per day. With two additional computers this increases to 23.6 million tasks per day.

Global computing uses Internet-connected PCs volunteered by their owners. These PCs are diverse, volatile, and error-prone. Sophisticated scheduling methods commonly applied in grid computing may not be sufficiently scalable and flexible for global computing environments. This paper shows that it is possible to classify global computing hosts based on simple metrics such as availability and reliability, and that it is efficient to assign tasks to such hosts accordingly. The proposed classification of workers is applied to P@H, a global computing project for protein structure prediction

What fraction of disks and other shared devices must be reserved to play an audio/video document without dropouts? In general, this question cannot be answered precisely. For documents with complex and irregular structure, such as those arising in audio/video editing, it is difficult even to give a good estimate. We describe three approaches to this problem. The first, based on long-term average properties of segments, is fast but imprecise: it underreserves in some cases and overreserves in others. The second approach models individual disk and network operations. It is precise but slow. The third approach, a hybrid, is both precise and fast.

Next-generation distributed systems will supportcontinuous media(digital audio and video) in the same framework as other data. Many applications that use continuous media need guaranteed end-to-end performance (bounds on throughput and delay). To reliably support these requirements, system components such as CPU schedulers, networks, and file systems must offer performance guarantees. Ametaschedulercoordinates these components, negotiating end-to-end guarantees on behalf of clients. TheCM-resource model, described in this paper, provides a basis for such a metascheduler. It defines a workload parameterization, an abstract interface to resources, and an algorithm for reserving multiple resources. The model uses an economic approach to dividing end-to-end delay, and it allows system components to “work ahead,” improving the performance of nonreal-time workload.

Comet, a UNIX/C++ toolkit for writing programs, such as teleconferencing systems and collaborative editors, that involve multiple users and use digital audio video, is described. Comet provides a simple programming interface: the application builds a graph of objects representing speakers and microphones, mixers, files, etc. Comet realizes the graph by creating and interconnecting processes and audio/video I/O servers. It handles implementation details such as process placement, data type conversion, and resource reservation.>

The Continuous Media File System, CMFS, supports real-time storage and retrieval of continuous media data (digital audio and video) on disk. CMFS clients read or write files in “sessions,” each with a guaranteed minimum data rate. Multiple sessions, perhaps with different rates, and non-real-time access can proceed concurrently. CMFS addresses several interrelated design issues; real-time semantics fo sessions, disk layout, an acceptance test for new sessions, and disk scheduling policy. We use simulation to compare different design choices.

Next-generation workstations will have hardware support for digital "continuous media" (CM) such as audio and video. CM applications handle data at high rates, with strict timing requirements, and often in small "chunks". If such applications are to run efficiently and predictably as user-level programs, an operating system must provide scheduling and IPC mechanisms that reflect these needs. We propose two such mechanisms: split-level CPU scheduling of lightweight processes in multiple address spaces, and memory-mapped streams for data movement between address spaces. These techniques reduce the the number of user/kernel interactions (system calls, signals, and preemptions). Compared with existing mechanisms, they can reduce scheduling and I/O overhead by a factor of 4 to 6.

Abstract DASH is a distributed operating system kernel. Message‐passing (MP) is used for local communication, and the MP system uses virtual memory ( VM) remapping instead of software memory copying for moving large amounts of data between virtual address spaces. Remapping eliminates a potential communication bottleneck and may increase the feasibility of moving services such as file services to the user level. Previous systems that have used VM remapping for message transfer, however, have suffered from high per‐operation delay, limiting the use of the technique. The DASH design reduces this delay by restricting the generality of remapping: a fixed part of every space is reserved for remapping, and a page's virtual address does not change when it is moved between spaces. We measured the performance of the DASH kernel for Sun 3/50 workstations, on which memory can be copied at 3·9 MB/s. Using remapping, DASH can move large messages between user spaces at a rate of 39 MB/s if they are not referenced and 24·8 MB/s if each page is referenced. Furthermore, the per‐operation delay is low, so VM remapping is beneficial even for messages containing only one page. To further understand the performance of the DASH MP system, we broke an MP operation into short code segments and timed them with microsecond precision. The results show the relative costs of data movement and the other components of MP operations, and allow us to evaluate several specific design decisions.

The DASH resource model is defined as a basis for reserving and scheduling resources (disk, CPU, network, etc.) involved in end-to-end handling of continuous-media (information flowing continuously over real time i.e. digital audio or digital video) data. The model uses primitives that express work-load characteristics and performance requirements, and defines an algorithm for negotiated reservation of distributed resources. This algorithm is embodied in the session reservation protocol, a backward-compatible extension of the Internet Protocol. Hardware trends and future applications that motivate the DASH resource model are described. The performance requirements for using continuous media and the limitations of existing systems are discussed. The DASH resource model for reserving and scheduling resources is presented. The DASH kernel is briefly described.>

Tarmac, a language system substrate on which systems for distributed parallel programming can be built, is described. A model of shared global state, called mobile memory, which is provided by Tarmac, is discussed. The basic unit of state in this model can be viewed both (1) as a block of memory that can be directly accessed by machine instructions and (2) as a logical entity with a globally unique name that may be efficiently located, copied, and moved. To support higher level synchronization models, the movements of a memory unit may optionally enable computations. The implementation and performance of Tarmac are discussed. Tarmac is contrasted with other systems for parallel distributed programming.>

Abstract RTAG is a system for automated implementation of communication protocols from formal specifications. The RTAG specification language is based on attribute grammars, and allows complex protocols to be specified concisely and with minimal need for additional program code. This paper describes a set of techniques for efficient automated implementation of protocols from RTAG specifications, and compares the performance to that of hand‐coded protocol implementations. We conclude that in many cases the performance of RTAG‐based protocol implementations is acceptable for experimental or production uses.

A computer music performance system (CMPS) is a computer system connected to input devices (including musical keyboards or other instruments) and to graphic and audio output devices. A human performer generates input events using the input devices. The CMPS responds to these events by computing and performing sequences of output actions whose intended timing is determined algorithmically. Because of the need for accurate timing of output actions, the scheduling requirements of a CMPS differ from those of general-purpose or conventional real-time systems. This paper describes the scheduling facilities of FORMULA, a CMPS used by many musicians. In addition to providing accurate timing of output action sequences, FORMULA provides other basic functions useful in musical applications: (1) per-process virtual time systems with independent relationships to real time; (2) process grouping mechanisms and language-level control structures with time-related semantics, and (3) integrated scheduling of tasks (such as compiling and editing) whose real-time constraints are less stringent than those of output action computations.

Marionette, a software package for distributed parallel programming in an environment of networked heterogeneous computer systems is described. It uses a master/slave model in which otherwise sequential application programmes can invoke worker operations (asynchronous remote procedure calls executed by slave processes) and context operations (updates to slaves' process states). The master and slaves also interact through shared data structures that can be modified only by the master. The Marionette runtime system is a heterogeneous remote procedure call package. It maintains the consistency of shared data structures, recovers transparently from slave processor failure, and assigns operations to slaves. The Marionette system includes tools for debugging, automated compilation of program binaries for multiple architectures, and distributing binaries to remote file systems. Measurements of a UNIX-based implementation to Marionette and a parallel ray-tracing renderer are presented.>

A communication abstraction called real-time message streams (RMS) is proposed. An RMS is a simplex (unidirectional) stream with several performance and security parameters that express the needs of RMS clients and the capabilities of the RMS provider. RMS providers can eliminate unnecessary or redundant work and can optimally schedule resources; RMS clients can use the parameters to select optimal methods for achieving reliability and flow control. RMS is the communication primitive of the DASH distributed system, which is currently being developed. The role of RMS in the DASH communication architecture and techniques and algorithms for providing RMS at different system levels are described.>

The RTAG (real-time asynchronous grammars) programming language is discussed. The language is based on an attribute grammar notation for specifying protocols. Its main design goals are: (1) to support concise and easily understood expression of complex real-world protocols; and (2) to serve as the basis of a portable software system for automated protocol implementation. The algorithms used in generating implementations from given specifications are sketched, and a Unix-based automated implementation system for RTAG is described.>

We propose a secure communication architecture for distributed systems that puts security below the transport level, and uses host-to-host rather than process-to-process secure channels. We argue that this provides the same level of end-to-end security as putting security at higher levels, and that it can simplify and improve the performance of transport protocols. The architecture is designed for very large distributed systems, which in general have security requirements beyond those of LAN-based systems.

A new methodology for specifying and implementing communication protocols is presented. This methodology is based on a formalism called “Real-Time Asynchronous Grammars” (RTAG), which uses a syntax similar to that of attribute grammars to specify allowable message sequences. In addition RTAG provides mechanisms for specifying data-dependent protocol activities, real-time constraints, and concurrent activities within a protocol entity. RTAG encourages a top-down approach to protocol design that can be of significant benefit in expressing and reasoning about highly complex protocols. As an example, an RTAG specification is given for part of the Class 4 ISO Transport Protocol (TP-4).