An Incentive System for Volunteer Computing

David Anderson
Janus Kristensen

Abstract
Volunteer computing uses large numbers of volunteered computers as a source of computing power and storage. Volunteer computing systems typically maintain computational credit, reflecting how much work has been done by each volunteer. Credit has no monetary value but is an important incentive for volunteers. A credit accounting system defines the units of computational credit, and allocates credit to entities such as volunteers, hosts and teams. In this paper we discuss the design of the credit accounting system in BOINC (Berkeley Open Infrastructure for Network Computing).

1) Introduction

Volunteer computing is a computing paradigm that uses large numbers of 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) [GIMPS], SETI@home [SAH], and Folding@home [FAH]. Volunteer computing is being used in high-energy physics, molecular biology, medicine, astrophysics, climate study, and other areas.

Volunteer computing participants have a wide range of motivations. Some are interested primarily by the science being done, others by the social aspects of the projects. One thing that nearly every participant wants is a numeric representation of their computational contribution. We call this credit, in the sense not of money but of acknowledgement.

A participant's credit can be presented in several different contexts. For example, Figure X shows the screensaver graphics of Einstein@home, which displays the participant's credit as a number. Figure X shows the BOINC Manager, which displays a graph of credit versus time. The purpose, in both cases, is to reassure the participant that he or she is continuing to contribute (or, if credit is not increasing, to alert the participant to problems).

Other contexts involve comparing the credit of volunteers or groups of volunteers. For example, Figure X shows a web page with a list of Einstein@home volunteers, ranked by credit. Figure Y shows a web page with a list of Einstein@home 'teams' (self-organized groups of volunteers) ranked by credit. Such pages (often called 'leaderboards') encourage competition between volunteers; to increase their standing on the leaderboards, volunteers may harness otherwise unused computers, upgrade existing computers, or buy new computers expressly for the purpose of getting more credit.

Competition between teams has an especially important role: team members recruit new volunteers (family, friends, co-workers) to their team for the purpose of increasing its ranking. This creates a 'viral marketing' effect that leads to exponential growth in the number of volunteers and the amount of computing power.

A graph of the number of active users on the SETI@home project (in blue, measured in thousands) and the amount of processing power contributed in average on a daily basis (green tint and dotted line, measured in million?/billion? Cobblestones) in the timeframe from August 2004 untill October 2005.

Another interesting context is 'signature images', typically used as signatures for message-board posts. These images show a compact list of the projects in which the person is participating, and the credit on each project (see Figure X).

SETI@home, which is representative of early volunteer computing projects, had a primitive credit system. It gave one unit of credit for each task, or 'workunit', completed. This system had many shortcomings. It didn't reflect the fact that some tasks used much more processing time than others. It gave credit even for incorrect results, which led to malicious users getting undeserved credit.

BOINC (Berkeley Open Infrastructure for Network Computing) is a middleware system for volunteer computing. It is being used by a number of volunteer computing projects, including SETI@home, Climateprediction.net [CPDN], LHC@home, Predictor@home, and Einstein@Home [EAH]. Volunteers participate by running a BOINC client program on their computers. They can 'attach' each computer to any set of projects.

1.1) Design Goals

In designing BOINC's credit system, we had two high-level goals:

  1. Participants should perceive the system as fair. They should not feel that other participants, in the same project or different projects, are getting more credit for comparable contributions.
  2. Credit should reflect utility to the project, so that if a participant takes an action to increase his credit (e.g. by upgrading computer hardware, or leaving the computer on or connected more of the time) it should contribute proportionally to the utility of the project.

These led to several subsidiary goals:

  • The system should be comprehensible to participants.
  • The system should be cheat-resistant.
  • The system should use a single measure of credit, include different resources (CPU, disk).
  • 3rd party sites should be able to combine credit across projects without gaining access to sensitive information.

1.2) Defining credit

How are we to define a unit of credit? We might say, for example, that the use of one gigabyte of disk storage for one day earns one unit of credit. But is this adequate? The storage probably has greater utility if the host is highly available and/or has a high-bandwidth network connection. Should we give more credit in that case? There are countless dimensions of this sort.

Given our goal of a single credit scale for incommensurable quantities (e.g., computation and storage) it is tempting to use the common denominator of money: the credit given for a resource is related to its cost. But cost to whom? There are two alternatives:

  1. The cost to the project of buying, managing and operating the resource
  2. The cost to the participant.
These may be quite different; for example, a participant may have a slow, energy-inefficient PC. Alternative 1) is preferable with respect to the two goals listed above.

A second general issue whether to grant credit when a resource is volunteered but not used. For example, a participant's PC might contact the project during a period when the project has no work, and then sit idle for an hour. Should credit be granted? From the participant's point of view, perhaps yes. However, it is not clear how this could be made cheat-resistant; while it's possible to show with high probability that a computer did work, it's not easy to show that it was willing to do work.

Finally, the magnitude of the credit scale is significant in terms of volunteer perception. A volunteer might find it discouraging to contribute a day of computer time and get 0.01 units of credit. Conversely, a inflated scale can lead to huge numbers that are hard to visually parse. BOINC's scale gives a typical computer about 100 units of credit per day.

2) Computation credit

Most applications that use BOINC do primarily floating-point-intensive computations. Therefore we decided to base computational credit on floating-point operations. Currently, the credit system doesn't reflect memory usage. {Nor does it take disk, network or GPU usage into account}

2.1 Generic benchmarking

Depending on how much the application developer wants to get involved, BOINC offers three ways of determining computational credit. The first of these is based on CPU benchmarks:

  • The BOINC core client runs a CPU benchmark (the Whetstone benchmark) which determines F, the number of floating-point operations per CPU second.
  • If an application executes for X CPU seconds, the claimed credit is XF.

This is a bit more complex on multiprocessors, since resources that are shared between processors may cause a CPU to get fewer FLOPS when other CPUs are running. The most extreme case is Intel hyperthreaded processors, in which each pair of CPUs share a single FPU. To reflect these factors, BOINC runs the benchmarks on all CPUs simultaneously.

There are a number of scenarios in which this mechanism doesn't work well:

  • The core client is compiled with a particular compiler, optimization flags, and target processor (typically generic and therefore unoptimized). Applications often are compiled for more specific architectures (indeed, BOINC's anonymous platform mechanism allows participants to compile applications themselves). Therefore, the application may get floating point operations per second than F, and the claimed credit will be too low.
  • {Since the core client is also available as source code it may be compiled with heavy optimizations that can optimize part of the benchmark away causing clients to request too much credit (and work) compared to the work that is actually performed with the unoptimized science applications.}
  • The Whetstone benchmark uses only a small amount of memory. Many applications use lots of memory, either randomly or sequentially. Therefore the actual number of floating-point operations per second can depend a great deal on the memory architecture and the size of CPU cache.
  • Some laptops have a hardware mechanism that dynamically changes CPU clock speed depending on factors such as battery time, and screen brightness. If benchmarks are performed while running on full speed (e.g. 2.8GHz) and the applications run while in low-power mode (e.g. 300MHz) the claimed credit will be too high.
These various factors cause a fairly high variance in claimed credit. Figure X shows the distribution of claimed credit for SETI@home.

SOMETHING ABOUT BENCHMARK WEIGHTING; PICTURE

2.2) Application benchmark

The second approach requires the application to implement its own benchmark. It may use a standard benchmark such as Whetstone, or preferably an application-specific benchmark that more closely mimics the application's memory access pattern and FP operation mix. The results of this benchmark are reported to the BOINC core client via an API call

boinc_fpops_per_cpu_sec(double x);
that must be made before the application terminates.

2.3) Application measurement

The third approach is for the application to do its own accounting of floating-point operations. This may be feasible for applications whose inner loop is deterministic and allows counting of FP ops (for example, FFT). The total number of FP operations is reported via an API call

boinc_fpops_cumulative(double x);
that must be made before the application terminates. {Have we got any measurements of how well these (all 3 benchmark methods) actually work across projects - does a computer get about the same credit or not for one day's work in seti compared to cpdn? This would be a valid success criteria.}

2.4) Redundant computation and credit

The claimed credit of a result, as with the output, cannot be trusted. A participant can modify the client software so that it returns an exaggerated claimed credit. A hardware or software problem can result in a claimed credit of zero.

BOINC provides a mechanism called persistent redundant computing, in which each task is performed on multiple computers. The results of these redundant computations are compared and are accepted as correct only if they agree. The number of instances required for a quorum, and the criteria for agreement, are project-specific.

This mechanism can be extended to minimize the impact of erroneously claimed credit. The idea is as follows: if n > 1 correct results are identified, with claimed credits C1 < ... < Cn, then

  • N=2: grant credit C1.
  • N>2: grant credit (C2 + ... + Cn-1)/(n-2) (i.e., throw out the low and high claimed credit and average the rest).
These policies limit the advantage gained by claiming exaggerated credit. ANALYZE THIS - IT DEPENDS ON THE VARIANCE OF CLAIMED CREDIT. {The implication of using the claimed/granted-system on _when_ credit is given compared to seti@home and other systems. This is a very important detail and one of the things that most users need a little time to get used to. Some never get used to the fact that others will have to verify the result before they can get the credit that they deserve. The delay is problematic because one of the reasons why credit exists is to compensate for missing direct scientific feedback (ie. it isn't possible to give scientific feedback on each and every WU (or is it?) so instead people get feedback on the progress in the form of credit). Alternatives: grant the claimed credit right away and correct later on when the average has been calculated and the result assimilated.}

2.5) Trickle messages and credit

Climateprediction.net has long jobs (months) so can't wait until the end to allocate credit. Allocate credit in trickle messages. Each message has summary of state (e.g. global temperature). Server message handler checks summary (quick and dirty cheating detection) then allocates credit based on fraction done.

3) Credit for storage and network transfer

Storage proof if server has a copy generate random string X have client MD5 with X, ensure result is correct if multiple clients have copy Network download direct proof: use 'has file' proof indirect proof: computed correct result (executable, input file) upload count bytes

4) Credit reporting and display

4.1) Total and recent average credit

For each entity (user, team and host) BOINC maintains and uses two credit-related quantities:

  • Total credit: the sum of all credit granted to the entity thus far.
  • Recent average credit: the average credit per day over a fairly short recent period (e.g. the last few days or week).

In our experience it is important to use both of these; for example, to have one leaderboard ranked by total credit, and another ranked by recent average credit. This rewards both new volunteers who contribute many computers (and thus get high recent average credit) and volunteers who join the project early and participate for a long time (and thus get high total credit).

In BOINC, recent average credit (RAC) is computed as an exponentially weighted average with a half-life of one week. In other words, if an entity is not granted any credit for one week, its RAC will decline by 50%.

An entity's RAC is updated whenever credit is granted. To avoid expensive database queries, the update is not able to scan the history of previous credit grants. The only information available is the previous RAC, and the time it was computed. BOINC uses the following approximation (all times are in days).

half_life = 7;
delta_t = now - last_update;
Weight = exp(-delta_t*ln(2)/half_life);
avg *= weight;
avg += (1-weight)*(work/delta_t);
In other words, we suppose that the credit was done granted at a constant rate R between last_update and now, a compute the new RAC as a weighted average of the old RAC and R, weighted to give the desired half-life if work is zero.

The above expression blows up (0*1/0) when now = last_update, i.e. when two credits are granted at the same moment. (This frequently occurs in practice). To address this, note that the limit as x -> 0 of exp(x) is

1 + x + O(x^2)
So as delta_t -> 0, weight approaches
1 - delta_t*ln(2)/half_life
so we have
(1-weight)*(work/delta_t)
~= (delta_t*ln(2)/half_life) * (work/delta_t)
= work*ln(2)/half_life)
So we can replace the last line with
if (1-weight > 1e-6) {
    avg += (1-weight)*(work/delta_t);
} else {
    avg += work*ln(2)/half_life;
}

4.2) Accounting group credit

Team membership is dynamic; users can quit a team and join a different one. There are two approaches to accounting credit for a team or other collection of users:

  1. A team's credit at a given point is the sum of the credit of its members at that point. (Hence, when a user joins or quits a team, the team's credit changes abruptly).
  2. When a user is granted credit, the user's current team is granted the same credit. (Hence, when a user quits a team, the team's credit doesn't change).
This distinction is more important than it seems. SETI@home used approach 1) and it led to situations where users with large credit capriciously switched teams, which weakened the team competition. Therefore BOINC uses approach 2).

Approach 2) can be efficiently implemented because teams have their own database records, which can be used to store total and recent-average credit. For other groupings of volunteers this is not the case. For example, each volunteer has an associated country (specified at signup, and mutable). The volunteers from a particular country form an implicit group, and there can be competition between countries. However, there is no separate database table for countries, so approach 1) must be used. Similarly for implicit groups such as 'users who own a single computer' or 'users who signed up in August 2003'.

4.3) Exporting credit data

BOINC-based projects can export statistics data as a set of compressed XML files available via HTTP (these files are generated by a BOINC utility program, which is typically run once a day). Examples of the XML elements:

<team>
  <id>5</id>
  <name>Broadband Reports Team Starfire</name>
  <total_credit>153402.872429</total_credit>
  <expavg_credit>503030.483254</expavg_credit>
  <expavg_time>1087542007.701900</expavg_time>
  <nusers>14</nusers>
</team>

<user>
  <id>12</id>
  <name>John Keck</name>
  <country>United States</country>
  <total_credit>42698.813543</total_credit>
  <expavg_credit>117348.653646</expavg_credit>
  <expavg_time>1087542007.701900</expavg_time>
  <cpid>283472938743489759837498347</cpid>
  <teamid>5</teamid>
</user>

<host>
  <id>102</id>
  <userid>12</userid>
  <total_credit>42698.813543</total_credit>
  <expavg_credit>117348.653646</expavg_credit>
  <expavg_time>1087542007.701900</expavg_time>
  <p_vendor>GenuineIntel</p_vendor>
  <p_model>Pentium</p_model>
  <os_name>Windows XP</os_name>
  <os_version>5.1</os_version>
  <create_time>1040170006</create_time>
  <timezone>28800</timezone>
  <ncpus>2</ncpus>
  <p_fpops>45724737.082762</p_fpops>
  <p_iops>43233895.373973</p_iops>
  <p_membw>4032258.064516</p_membw>
  <m_nbytes>670478336.000000</m_nbytes>
  <m_swap>1638260736.000000</m_swap>
  <d_total>9088008192.000000</d_total>
  <d_free>3788505088.000000</d_free>
  <n_bwup>24109.794088</n_bwup>
  <n_bwdown>57037.049858</n_bwdown>
  <avg_turnaround>465609.562145</avg_turnaround>
  <host_cpid>e129b5fa44ed8ba58e41c472822f2807</host_cpid>
</host>

4.4) Cross-project user identification

Accounts on different projects are considered equivalent if they have the same email address (we have considered other concepts, but they all lead to extreme complexity).

Projects can't just export email addresses in statistics files; email addresses are private. It's also not desirable to export hashed email addresses, because spammers could enumerate feasible email addresses and compare them with the hashed addresses.

Instead, BOINC uses the following system:

  • Each account is assigned an 'internal cross-project identifier' (CPID) when it's created; it's a long random string.
  • When a scheduling server replies to an RPC, it includes the account's CPID, its email address, and its creation time. These are stored in the client state file.
  • When the BOINC client makes an RPC request to a scheduling server, it scans the accounts with the same email address, finds the one with the oldest creation time, and sends the CPID stored with that account.
  • If the scheduling server receives a CPID different from the one in its database, it updates the database with the new CPID.
  • User elements in the XML download files include a hash of (email address, CPID); this 'external' CPID serves as a unique identifier of all accounts with that email address. (The last step, hashing with the email address, prevents people from impersonating other people).

This system provides cross-project identification based on email address, without publicizing any information from which email addresses could be derived.

4.5) Host identification

Each host generates a random internal cross-project ID This is reported to the projects that to which the host is attached. The projects convert it to an external cross-project ID by hashing it with the owner's email address; this prevents spoofing. The external ID is exported in statistics files.

4.6) Credit statistics web sites

A number of web sites have been created to show BOINC credit statistics. They typically maintain relational databases with tables representing entities (accounts, hosts, teams) both on particular projects, and aggregated over all projects. They may maintain entities (e.g. countries, single-computer participants, etc.) that are not explicitly maintained in the projects' BOINC databases. These tables are indexed so that ranges of entities (according to total or recent-average credit order) can be efficiently enumerated. Periodically (typically once per day) they download XML statistics data from all BOINC projects and update the database tables.

The sites offer web pages that show leaderboards, i.e. lists of top users, hosts, or teams, or of derived groups such as countries, operating systems, or processor types. These boards may be filtered according a range of criteria: for example, a page might show the top Macintosh owners in Paraguay. With some additional database complexity, the sites can show historical data: e.g. the change in leaderboard rankings over the past month. This type of data is very good at fueling team competition.

In addition, the sites may offer other web-based services, such as

  • A web RPC that shows the cross-project credit totals for a user or team,
  • A web RPC that returns a GIFF image showing credit figures, to be used as a message-board signature.
  • An RSS feed that returns automatically-generated news items when an entity achieves a particular credit level, or when its ranking changes on a leaderboard.

4.7) Cross-project issues

What if a project gives more credit per FLOP than others? What if a project gives credit 'prizes'?

5) Related work

Economic systems Not relevant to volunteer computing. In economic systems, the owner of a resource tries to make as much money as possible. Here, the owner

United Devices

6) Conclusion

There is extensive discussion on BOINC message boards about

  • The economics of credit: how to maximize the ratio of credit to initial investment, and the ratio of credit to recurring cost (e.g. power consumption).
  • Maximizing credit across a range of projects and hardware types. Volunteers have discovered that different processor types get credit from different projects at different rates. For example, a Pentium might get more credit per day from project A than project B, while the reverse is true for an AMD Athlon. So a volunteer who owns one of each can get more credit by running project A on the Pentium, and project B on the Athlon.

Future work:

  • take RAM into account {and network, disk, GPU, DSP etc. Do we need a seperate number for those or can it be combined? etc)}
  • {The idea of spendable credit - trading CPU power between users}
Brainstorming ----------------- Goals - Competition - More work done - Progress - Feedback - Stuff is working - Value to users - Instead of direct scientific output - Measuring their contribution - A way to "pay back" electricity etc. Success/error - Understanability - Reference machine (easy enough to understand?) - RAC, credit granting, delays - Precision - Fairness - Evenness across platforms/projects - => Comparability - Stats - Used to measure project performance Other credit systems - A look at BOINC compared to seti classic - ? Where do we go from here - What needs to be changed - Evenness across platforms - More concrete reference machine? - What could be added - More kinds of credit (GPU, DSP, disk/network etc) - Spendable credit - ? - What works perfectly as is ------------------- from SETI@home message boards: It looks like the time for a Paris core Sempron 3100 crunching the seti ref workunit is about 330~550 seconds longer than the A64s 3K+. So that will result in the A64 crunching a the SETI WU in about 102 minutes vs. 112 for the S64. So, not allowing for the electric bill difference I think the crunching output of the three S64s is going to distance the two A64s pretty fast. I think the bottom line here is, you are right if it's not a dedicated cruncher that has to do other things but for a dedicated 'basket cruncher' hard to beat the S64 bang for the buck. I hung onto the T-Bird/Thorton/Barton chips for a long time because of the performance/price ratios... but now the semprons are as cheap or cheaper. There's a point where this turns around the other way. I found stacks of Dell PII and PIII machines a week or two ago for $25 to $90 and thought "wow" I'll just buy a bunch of these... but they are over the curve already and I can get more crunch power per $ by building a new $200 basket cruncher than a room full of PIIs ESPECIALLY if you facter in the increased A/C costs and power draw of the old PIIs themselves. Thanks for making me look at the numbers a bit closer and working this out... the A64s are closer in price than I thought they were. -- Skip I have ALL Windows machines in my "ranch", a "ranch" is the next step up from a "farm", over 15 machines they tell me, ANYWAY I use Win2k for most of my machines but Me and of course XP, both home and pro. I have stayed away from 98se but think it will work fine. Networking is going to be the hardest part, I have at least one computer on each floor of my house. I have 1 on the main floor, a wireless laptop. I have 5 on the top floor, a mix of wired and wireless. and 18 in the basement, they are all wired but go thru a hub and a switch to an access point that is then wireless to the top floor to a second access point. This helped keep me from running wires from the top floor to the basement. I would definately say that networking is the most expensive part, nic cards can be gotten on sale for about 5 dollars US, less at computer shows. But routers and access points and hubs and switches etc are not, they can be gotten cheaply but only comparitively so. Remember that Seti Boinc needs at least 64 meg of ram FREE after the OS loads, so go for at least 128 meg of ram minimum in each machine that is Boinc only. I use harddrives that are left over from earlier upgrades, I do upgrades for friends computers and have TONS of "stuff" laying around. I usually use the friends old harddrive in a machine but if it starts crashing I keep my eyes on the sales and will pay less that $50.00 for a 120 meg or less drive. This has given my "ranch" some stability that it sorely needed. I use radmin instead of VNC, I think it is easier. I usually buy empty cases and build my machiens from old parts but I do also get new stuff on sale. I have been known to buy AMD mb's WITH cpu AND ram for under $100.00 at TigerDirect. I usually get a mb with the video built in but not always, I found at the local CompUSA a bunch of 8 meg video cards on sale for $10.00 each one time and bought 5. I still have 2 unused. I have computers that friends get from dumpsters that I plugged in and run fine! Loaded with software and everything!!!! Slow for me, the latest is only a 450mhz, and that is the slowest in the "ranch". I will donate it to a needy person soon. ALL the rest of the "ranch" is over 1ghz in cpu speed, I have weeded out the slower ones. Soon I will weed out some more and donate them to other friends. Usually I give it to the kids of friends and they like it because it is better than nothing. They are NOT gaming machines but will go on the net and do wordprocessing etc. This has gotten waaaay too long so I will stop here. GOOD LUCK and if you don't know something someone here can help you or provide a link that can. -----------