• target system
• simulator
• model
• volunteer (not participant)
• volunteer computing (not global computing)
• dispatch (not send)
• Job (before section 2.2; after that, Job instance)

1) Introduction

Volunteer computing is a computing paradigm that uses large numbers of personal computers, volunteered by members of the general public, to provide computing and storage resources. Early volunteer computing projects include the Great Internet Mersenne Prime Search (GIMPS) [REF], distributed.net [REF], SETI@home [ref], and Folding@home [REF]. Volunteer computing is being used in high-energy physics, molecular biology, medicine, astrophysics, climate study, and other areas.

Volunteer computing, in contrast with Grid computing, uses resources controlled by individuals who are not accountable to the computing project and cannot be trusted by it. The resources are dynamic, highly diverse in many dimensions, and sporadically connected. The volunteers must be provided with incentives such as a "credit system" that tracks (in a fraud-resistant way) the resources they have contributed.

The Berkeley Open Infrastructure for Network Computing (BOINC) [REF] is a middleware system developed to meet the requirements of volunteer computing. BOINC facilitates the creation of autonomous volunteer computing projects. It allows computer owners to selectively participate in these projects, and to control the allocation of their resources among the project. BOINC is currently used by a number of projects, including SETI@home, Climateprediction.net [REF], and LHC@home [REF].

Einstein@home [REF] is a volunteer computing project based on BOINC. PASTE TEXT ABOUT E@H HERE. Einstein@home has been in operation since February 2005 and currently has about 60,000 participating hosts, which supply on average X years of computing time per day.

BOINC implements a number of features and mechanisms to support the requirements of volunteer computing; for example, it supports "persistent redundant computing", which can be used to detect and recover from erroneous or lost results. Some features of BOINC were added specifically to meet the needs of Einstein@home. For example, we added a scheduling policy called locality scheduling that attempts to minimize network traffic by preferentially assigning tasks using data files already resident on the computer.

Each mechanism typically involves interacting client and server scheduling policies. There are also many interactions among the mechanisms. For the most part, the mechanisms used by Einstein@home and BOINC have been developed in situ, that is, by deploying them on the "target system" (the operational project) and observing the resulting change in system performance. This approach has several drawbacks:

• Changes in performance may be due to factors other than the policy that was modified;
• Poorly-performing policies could reduce the target system's performance.
• Mistakes or poor choices could drive away participants.
• It is difficult to predict the performance of the mechanisms. Often, isolated factors (such as a single misbehaving host) have a large impact on system performance.

Instead, we decided to study BOINC mechanisms by software simulation. We developed a discrete-event simulator that models the entire Einstein@home system at a fine granularity (individual hosts, jobs, and files). Mechanisms such as redundancy and locality scheduling are replaceable modules in this simulator. Using the simulator, we can predict the performance impact of changes in these policies, or of future policies.

In Sections 2 and 3 we describe the aspects of BOINC and Einstein@home that are relevant to system performance. In Section 4 we describe the simulator and the model on which it is based. We validate the simulator by comparing its output with measurements of the target system. In Section 5 we use the simulator to compare alternative task assignment policies. Section 6 discusses related work, and Section 7 offers conclusions.

2) Relevant aspects of BOINC

BOINC involves the following entities:

• A project is an organization (typically a scientific research group) that solicits volunteered computing power. A project is created by developing or porting an application, installing and running the BOINC server software on a server computer, and publicizing the URL of the server. Projects are autonomous. BOINC has no certification process or central registry for projects.
• A volunteer is a computer owner who donates computing resources to one or more projects.
• A host is a computer owned by a volunteer. The volunteer installs a program called the BOINC client on each such computer, and configures the client to attach to a set of projects.

The BOINC server software involves a number of interacting components, which interact via a common relational database (typically MySQL). These components include online servers, back-end daemons, and Web interfaces. The component relevant here is the scheduling server, which is responsible for dispatching work.

2.1) The BOINC client

The BOINC client controls resource usage on a host; it manages application execution, file transfers, and disk usage. Volunteers can specify a number of preferences that govern the behavior of BOINC on a host H. These preferences include:

• The resource share of each project. This determines the fraction of bottleneck resources (such as CPU time) allocated to each project.
• The desired time interval between network connections, denoted ConnectInterval(H). This is useful for modem-connected computers or portable computers that are sporadically connected.
• Whether BOINC should do work (computation or communication) only when there has been no recent input activity.
• Times of day during which BOINC may do work.
• How much disk space and memory BOINC may use.

All communication in BOINC is initiated by the client and uses HTTP (Hypertext Transfer Protocol [REF]). Thus the client can be used behind firewalls and proxies that allow outgoing web traffic. The client periodically issues a scheduler request to a scheduling server of each project to which it is attached. The request message includes

• A list of completed tasks.
• A list of the project's data files on the host.
• A description of the host's hardware, including CPU benchmarks, memory size, and free disk space.
• A request for a certain amount of additional work (expressed in terms of how much wall-clock time the tasks should occupy).

The client issues a scheduler request to a project when either 1) it needs more work from the project, or 2) a completed task is close to its deadline. The client attempts to separate scheduler requests by at least ConnectInterval(H).

2.2) Persistent redundant computing

Grid computing [REF] involves resource sharing between organizations that are mutually accountable, and in each of which resources are centrally managed. In contrast, a person who participates in a volunteer computing project is not accountable to the project (indeed, their identity is unknown), and volunteered hosts are unreliable and insecure.

When a task is sent to a host, several outcomes are possible:

• The correct output is returned to the project. Because of differences in floating-point computation between processors, there is not necessarily a unique 'correct' output [TAU]. BOINC projects must write an application-specific function that compares a set of outputs, sees if a quorum of them 'match' (i.e. are sufficiently similar), and if so selects one of the quorum as the canonical result.
• Incorrect output is returned to the project. This can happen because of a hardware malfunction (especially in hosts that are 'overclocked'), because of an incorrect modification to the application (some BOINC projects are open-source) or because of a malicious intentional attack by the volunteer.
• The application crashes, and the client reports the error to the server.
• There is never any response to the project, e.g. because the task never arrived, the host dies, the host stops running BOINC, or the volunteer performs an action (such as resetting the project) that causes tasks to be lost.
• A nonrecoverable error occurs while downloading or uploading files.
• The result is computed (possibly correctly) but is reported too late to be of use.

A job is a computational task. It specifies a set of input files and an application program. Each job J has several scheduling-related parameters:

• DelayBound(J): a time-out interval for instances of J.
• NResults(J): the number of instances of J to create initially.
• MinQuorum(J): the minimum size of a 'quorum' (see below)
• Estimates of the amount of computing, disk space, and memory required to perform the computation.
• Upper bounds on the permitted number of erroneous, correct, and total results. These are used to detect workunits that consistently crash the application, that return inconsistent results, or that cause their results to not be reported, respectively.

Each job has several job instances. Each job instance specifies a set of output files. A job instance is said to be dispatched to a host when it is included in a scheduler reply message. A job instance is dispatched to at most one host. A job instance is said to be reported when it is listed in a scheduler request message.

Each job instance has a state field whose values include unsent, in progress, reported, and timed out. If sufficient instances of a job have been reported and match, they are marked as valid and one of them is selected as the job's canonical instance. An example is shown in Figure X.

BOINC implements persistent redundant computing as follows:

• When a job J is created, NResults(J) instances are created and marked as unsent.
• When a BOINC client requests work, the project's scheduler selects one or more job instances that are unsent and are feasible for the host (i.e., the host has sufficient memory and disk, and is likely to complete the result by its deadline) and dispatches them to the host. To prevent cheating or manipulation, two or more instances of the same job are never sent to the same participant. The job instance's deadline is set to the current time plus DelayBound(J).
• If a job instance's deadline is passed before it is reported, the server marks it as timed out, and checks whether the limit on the number of error or total results for J has been reached, and if so marks J as having a permanent error. Otherwise creates a new unsent instance of J.
• When a job instance I is reported, and its job already has a canonical instance IC, the scheduler invokes an application-specific pair validation function that compares I and IC, and marks I as valid or invalid accordingly. Otherwise, if the number of successful instances is at least min_quorum(J), the scheduler invokes an application-specific set validation function which, if it finds a quorum of equivalent instances, selects one of them as the canonical instance, and marks the instances as valid if they match the canonical instances.

Because a job's instances are sent at random to different participants, consipiracy would be needed for a maliciously incorrect instance to be accepted as valid.

Volunteers are granted credit for valid job instances. Credit is granted to a job instance when it is marked as valid. Credit is an important incentive for volunteers; it provides a basis for competition, it tells them if they are successfully contributing or not. Hence it is important to limit the delay between when a job instance is reported and when it is granted credit.

2.3) Dealing with ill-behaving hosts

Some hosts, upon being sent a job instance, immediately (within a few seconds) report a failed outcome and request more work. This may happen because of a software configuration problem or malfunctioning hardware. It may happen because a malicious user is attempting to get multiple instances of the same job, to circumvent the redundancy checking mechanism. To deal with this problem, BOINC uses the following punishment policy:

• For each host, the server maintains a limit N on the number of job instances sent per day. This is initially K times the number of CPUs, where K is a project-specified parameter (8 for Einstein@Home).
• When an error instance is returned, or an instance times out, N is decremented down to a limit of 1.
• When a successful instance is returned and validated, N is doubled.

A second class of misbehavior is when a host repeatedly contacts the scheduler, claiming to be a new host each time. This results in the creation of a new host record and the dispatch of a job instance. Currently this problem is dealt with manually, by identifying and emailing the participant. We are considering adding a 'governor', e.g. requiring the participant to perform a web interaction for each N hosts created.

3) Einstein@home

TEXT ABOUT THE SCIENCE OF E@H

TEXT ABOUT THE DATA SERVERS

Einstein@home's input files are X MB. Each file is analyzed with Y different parameter sets. Each analysis uses approximately Z floating-point operations, or X CPU hours on a 1 GigaFLOPS machine.

Einstein@home uses the following parameters for all workunits W:

• NResults(W) = 4
• MinQuorum(W) = 3
• DelayBound(W) = 7 days

Locality scheduling

4) Simulating Einstein@Home

In this section we describe the various components of the model, and then compare the simulator's output to the observed behavior of the target system.

Our goal in this work is to study a particular server-side scheduling policy. From this perspective, many aspects of the target system (such as the processing and reporting of job instances by hosts) are stochastic processes for which we care about the external behavior, but not the internal details. Therefore our simulator does not seek to model these internal details.

Furthermore, we seek to model the external behavior of such processes accurately, but not necessarily to describe them analytically. Therefore we model many of these process by extracting data from the target system, computing a histogram, then (in the simulator) using histogram-based random number generators for which the probability of each outcome exactly matches its frequency in the observed data. This relationship is shown in Figure X. Note that while this method models individual distributions well, it may fail to model correlations.

4.1) Modeling host arrival and lifetime

Volunteer computing projects typically have a startup period during which they acquire large numbers of volunteers, followed by periods of slow growth, statis, or decline. For example, the rate of host arrival for Einstein@home (i.e. the number of new hosts per day) is shown in Figure X. The peaks that appear near day 0, day 25 and day 40 are when test users were given accounts. The large peak at day 51 coincides with the formal launch of the project, when the general public was invited to sign up.

Figure X: New hosts per day with total credit > 0

Our goal is to model behavior of scheduling policies in the steady state, i.e. when the number of hosts is stable. Even during this period there is churn as volunteers join and leave the project, and as they attach and detach hosts. This effect is relevant to scheduling because the last job instances issued to a host are never reported.

To model the host arrival process, we extracted the lifetimes of hosts in Einstein@home (i.e. the interval between first and last RPCs for hosts that haven't done an RPC in the last 30 days).

Figure X: distribution of host ages. RPC time - create time for hosts where total credit > 0, RPC seqno > 0

Figure X: distribution of host lifetimes. RPC time - create time for hosts where total credit > 0, last RPC time older than 20 days.

The number of active hosts (i.e. those that have been granted credit within the last 10 days) is shown in Figure X.

Figure X: the number of active hosts. #hosts with RPC time in last week, and total credit > 0.

Hence our model assigns a lifetime to each host, based on the histogram of lifetimes shown in Figure X.

In our model host arrival is a Poisson process. If we use the observed mean arrival rate from Figure X, there are too few mean active hosts, because the distribution of host lifetimes doesn't reflect hosts that have joined and not left. To correct for this, our model uses a host arrival rate such that the mean active hosts is the observed value.

4.2) Modeling job instance processing and reporting

In the target system, the handling of a job instance by a host involves several steps:

1. The client makes a scheduler request and receives descriptions of the job and the instance.
2. The client downloads the job's input files and the application files, if they are not already present on the host.
3. The job instance is queued, awaiting execution.
4. The job instance executes. This execution may be interrupted when the job instance is preempted by other job instances, when the computer is powered off, or when BOINC is not active.
5. The job instance is completed.
6. The job instance's output files are uploaded.
7. The client makes another scheduler request, reporting the completed job instance and receiving an acknowledgement, after which it deletes its record of the job instance.

These events may be interleaved and may occur in parallel for the job instances handled by a given host. The behavior of a host H depends on its network connection interval ConnectInterval(H). Hosts for which ConnectInterval(H) is small relative to job instance execution times typically behave as shown in Fig. X: each job instance is reported immediately after its completion, and the next job instance is obtained and started immediately (file download and upload are omitted for simplicity).

A host for which ConnectInterval(H) is several times the mean execution time might behave as shown in Fig x. In this case there is a delay between a job instance's completion and when it is reported.

Hence the latency of a job instance (the time from dispatch to reporting) can depend on the host's network connection interval. The distribution of network connection intervals is shown in Fig. x

Figure X: Network connection intervals

The time needed to complete a task on a given host can depend on a number of factors:

• The input data. (For Einstein@home this factor doesn't vary much - the number of FLOPs is more or less constant across job instances).
• The speed of the host's CPU and memory system.
• The fraction of time the host is powered on and BOINC is running.
• The fraction of time in which BOINC is allowed to do work, based on user preferences.
• The other BOINC projects in which the user participates, and their resource shares.
• The time needed to download input files and upload output files.

We extracted the distribution of host throughputs (average number of successful results per day) from Einstein@home. The result is shown in Fig. x

Figure X: The distribution of job instance latencies

Our simulator models work fetching and reporting as follows:

• Each host H is assigned a 'processing rate' T(H) from the distribution C.
• Each host H is assigned a network connection interval ConnectInterval(H) from the distribution I.
• The dispatching of job instances to H is modeled as a Poisson process with rate T(H).
• The processing time P for a given job instance R is T(h)*X, where X is a random number sampled uniformly from (0.75, 1.25).
• The report time for a given job instance R is its dispatch time plus P(H), rounded up to a multiple of I(H) from the host's creation time.

4.4 Modeling host errors

Study of the Einstein@Home database reveals that hosts fall into four main categories.

A: Approximately 25% of hosts are 'perfect citizens' and do not produce any errors.

F: Approximately 30% of hosts contact the scheduler a single time, are sent job instances, and never contact the scheduler again. This category of hosts has a 100% error probability but a short lifetime. They correspond to volunteers who install and start the software, but then either lose interest immediately or have failed to install the software correctly.

D: Approximately 5% of hosts contact the scheduler a few times but also have a 100% error probability. An additional 5% of hosts contact the scheduler many times (more than thousands) with a 100% probability. These are typically hosts for which networking or installation problems prevent the host from doing useful work, but do not prevent it from making regular contact with the scheduler and downloading work. We model this 10% of hosts with the same distribution of lifetimes used for successful hosts and a 100% error probability.

B: We do not have good data on the remaining 35% of hosts. There is weak evidence that suggests that these hosts have a uniform distribution of error rates ranging between 0 and 1, so without strong justification, we model them in this way.

We do have good statistics on the overall number of failed job instances. On average, 13% of all job instances fail (client error, not returned to server, etc.). Hence, we adjust the relative percentages of hosts in categories A and B in order to obtain, within our simulation, an overall average error rate of 13%.

4.6 Validating the simulator

Figure X: Distribution of latencies of valid job instances. receive_time - send_time for job instances that are valid.

Figure X: Distributions of time from job creation until a) a canonical instance is found, and b) all instances of the job have timed out or been reported.

5) Studying the performance of task assignment policies

5.1) Task assignment policies

Each Einstein@home task analyzes a 14 MB file. There are 150 tasks (each with different analysis parameters) per file. We now return to the problem of

The server's task assignment policy decides what tasks to send. In a data parameter sweep application this policy typically attempts to dispatch tasks to computers that already have the necessary input files. This reduces total network traffic. In the context of volunteer computing there are other factors, such as the need to replicate tasks and grant credit expeditiously. Einstein@home has developed and experimented with task assignment policies that address these various goals.

task assignment for parameter sweep applications. We frame this problem as follows (see Figure 4). The project's overall workload involves of an unbounded sequence of files. For each file there is a set of N jobs, each representing a particular set of of parameters to be used in the analysis of the file. For each job there are several instances (the number of instances reflects the project's redundancy parameters). jobs and files are created dynamically as needed. The initial set of instances for a workunit are created together, at the same time as the job.

For simplicity we will assume that each host handles one job instance at a time. Then when a host contacts the scheduling server, the request message includes a completed job instance (except for the first request), a host identifier, and a list of files present on the host. The scheduling server returns a new job instance to be processed by the host. In particular, it may:

• Return an existing unsent job instance;
• Create a new job for an existing file, and return one of its instances.
• Create a new file and a new job for that file, and return one of its instances.

Once a host has been sent a file, it can execute a sequence of job instances for that file without incurring additional network bandwidth. For redundant computing with redundancy N, each task must be done by N separate hosts, so each file must be sent to at least N hosts. In the ideal case, these hosts proceed in parallel through the file's workunits, and the file isn't sent to other hosts (Figure 3a).

When a host fails to complete a result successfully (e.g. because it stops participating) its place must eventually be taken by a new host (see Figure 3b, where host H5 replaces host H1).

If one of the hosts is much faster than the others, then it can get unboundedly far ahead in the job sequence (see Figure 3c). Because credit is granted only when job instances are validated, this can lead to increasingly long delays in credit granting for the fast host. This can be solved either by sending the fast host an additional file and alternating its work between the two files (thus slowing down its progress on this file) or by sending this file to additional hosts.

Two underlying assumptions should be clarified. First, we assume that server file storage space is abundant, so there is no incentive to accelerate the completion of all the work for a file by sending it to additional hosts. Second, although in fact the set of files in a given project is finite, we assume that it is large enough (relative to the number of hosts) that it can be treated as unbounded.

5.2) Performance metrics

There are several figures of merit by which task assignment policies can be evaluated:

• The average network bandwidth used. Bandwidth may be scarce and/or expensive at the server end.
• The rate at which jobs are completed.
• The statistics of credit lag time (the interval from when a correct job instance is reported to when it is granted credit). Users become dissatisfied if credit lag time is high.
• The statistics of disk space usage on client hosts.
• The statistics of disk space usage on the server.

These metrics are partly independent. Their relative importance is project-dependent.

Algorithm 1

(Revision 1.1, checkin Sept 9 2004)
function send_new_file_work
    send result R with lowest ID such that
        no result R2 with R.wu == R2.wu has been sent to U
    if none:
        create new file f
        send result R from f with lowest ID

function send_results_for file(f)
    send result R with lowest ID such that
        R.file == f
        no result R2 with R.wu == R2.wu has been sent to U

if F is empty
    send_new_file_work()
else
    for f in F
        if send_results_for_file(f) break
        

Algorithm 2

(rev 1.24 Jan 11 2005 5:18)

This seems to be the same as algorithm 1
except that files are generated dynamically.
Let's skip it.

Algorithm 3

(rev 1.33 Jan 17 2005 19:20)

If there's an unsent result R older than 7 days, and feasible, send it

if F is nonempty
    for f in F
        if send_results_for_file(f) return

If there's an unsert result R older than 2 hours, send it

Select a file f randomly from the set of files with unsent results
    if send_results_for_file(f) return
    for all unsent results R, enumerated starting from f
        is feasible, send

Algorithm 4

(rev 1.45 Feb 15 2005 21:18)

6) Related work

7) Conclusions and future work

4.5 Simplifications

Our simulator simplifies or omits many aspects of real system behavior. A partial list:

• scheduler may send multiple job instances
• clients have limited disk space.

References

Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov, and Francine Berman. Heuristics for scheduling parameter sweep applications in grid environments. In Heterogeneous Computing Workshop, pages 349--363, 2000. http://citeseer.ist.psu.edu/casanova00heuristics.html

A. Takefusa, H. Casanova, S. Matsuoka, and F. Berman. A study of deadline scheduling for client-server systems on the computational grid. In Proceedings of 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10), pages 406--415, 2001. http://citeseer.ist.psu.edu/takefusa01study.html

LU, D., AND DINDA, P. A. Synthesizing realistic computational grids. In Proceedings of ACM/IEEE SC 2003. http://citeseer.ist.psu.edu/lu03synthesizing.html

P. Dinda. Online prediction of the running time of tasks. In Proc. 10th IEEE Symp. on High Performance Distributed Computing, (to appear) 2001. http://citeseer.ist.psu.edu/dinda01online.html

H. Song, X. Liu, D. Jakobsen, R. Bhagwan, X. Zhang, K. Taura and A. Chien, The MicroGrid: a Scientific Tool for Modeling Computational Grids, Proceedings of IEEE Supercomputing (SC 2000), Nov. 4-10, 2000, Dallas, USA. http://citeseer.ist.psu.edu/song00microgrid.html

Reinhardt, S., Hill, M.D., Larus, J.R., Lebeck, A.R., Lewis, J.C., and Wood, D.A., "The Wisconsin Wind Tunnel: Virtual Prototyping of Parallel Computers," Proceedings of the ACM Sigmetrics Conf. on Measurements and Modeling of Computer Systems, pp. 48-60, May 1993. http://citeseer.ist.psu.edu/reinhardt93wisconsin.html

author = "Kento Aida and Atsuko Takefusa and Hidemoto Nakada and Satoshi Matsuoka and Umpei Nagashima", title = "A Performance Evaluation Model for Effective Job Scheduling in Global Computing Systems", booktitle = "{HPDC}", pages = "352-353", year = "1998", url = "citeseer.ist.psu.edu/284732.html"

D. Abramson and J. Giddy, "Scheduling Large Parametric Modelling Experiments on a Distributed Meta-computer", PCW '97, September 25 and 26, 1997, Australian National University, Canberra, pp P2-H-1 -- P2-H-8. http://citeseer.ist.psu.edu/abramson97scheduling.html

R. Buyya, D. Abramson, and J. Giddy, Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid, HPC ASIA'2000, China, IEEE CS Press, USA, 2000. http://citeseer.ist.psu.edu/buyya00nimrodg.html

G. Shao, R. Wolski, and F. Berman. Performance effects of scheduling strategies for master/slave distributed applications. Technical Report CS98-598, University of California, San Diego, 1998. http://citeseer.ist.psu.edu/wolski98performance.html

GIMPS

SETI@Home

Folding@home

Grid

Taufer homogeneous

Petri nets, queueing systems