We consider a reliable desktop grid solving multiple tasks with answers from a given set. Wrong answer can be obtained with some small probability p: reliability means that p is small with respect to 1 p. Penalty is added to the computation cost if a wrong answer is believed to. We consider the optimization problem of choosing the quorum in case of nite set of possible answers, countable set, and set with continuously distributed subset.
In the presented work we consider the problem of task scheduling in a Desktop
Grid. The term stands for a distributed computing system with computational
nodes voluntarily donated by an organization (or a group of organizations
following the same research goals) in their idle time. The nodes of such system
are desktop PCs, compute servers, cluster nodes, and other computational
resources available in a local network and/or the Internet. The BOINC middleware
[
Let us consider a desktop grid computing system that consists of multiple computers and solves numerous similar tasks. Each task has an answer from some set of possible answers. Without loss of generality we can assume that this set is a subset of real numbers or integer numbers. The correct answer is obtained with some probability q. Errors are possible due to malfunction of hardware, malicious actions, or wrong answers produced by a correct non-deterministic algorithm. Other, wrong answers have the total probability 1 q; some of them can have non-zero probability, others are distributed continuously.
Such errors can be made less likely by replication: sending copies of each task to di erent computing nodes until a chosen number of identical answers is received. This number is called the quorum. Obviously, for a given quorum the number of copies is at least but can be more, up to N ( 1) + 1 for nite number N of possible answers. However, the average number of copies is nite even in case of in nite set of answers.
If a wrong answers is taken, this error will later be revealed and can cost much. The losses can be connected with loosing a rare desired phenomenon, unnecessary expensive laboratory checks, reputational losses, etc. These penalties can be huge compared to the average cost of a single task.
Here we assume that q 1 in the following sense: 1 q is negligibly small compared to q. Therefore we can neglect possible cases of choosing between di erent wrong answers or any wrong answers seen if the correct one has been believed.
First we consider the nite set of possible answers. Then we will add some simple notes about more general case with in nite set of answers, with positive probabilities and/or continuously distributed. 3
Assume that M + 1 possible answers have probabilities pm, p0 = q 1 (the correct answer), penalties of di erent answers are Fm, F0 = 0. If quorum is chosen and the correct answer is accepted, the average number of copies is up to the precision discussed above, the probability to get the correct answer is q. However, for each wrong answer number m possible durations can be any between (the same wrong answer in a row) and 2 1 (after 1 correct and 1 wrong answers the nal wrong answer was received). The corresponding probabilities of durations + i, i = 0; : : : ; 1 are, respectively, equal to The rst factor chooses i positions of correct answers among while the nal answer is accepted.
The mean cost is
i. To prove this equality, we need two well-known formulae (the Pascal On the nal step we applied the obvious equality the proof.
Now we can rewrite the mean cost as nn = nn 11 . This completes We want to minimize this cost keeping in mind the fact that penalties Fm are not known precisely, so that conditions should allow variations of Fm. Let us consider di erences E = E( + 1) E( ) and take the rst with E 0. It is easy to check that
n m : 2 = (1)
M X Fmpm m=1 1: (2)
It is clear that inequality (2) holds, then each term is less than 1; although it is possible to choose parameters in such a way that all terms are less than one while the sum is more. However, if we take making each term less than 1, di erence between optimal value is at most 1.
Let us simplify condition (2) in case M = 1 using the asymptotical formulae 2
22 = p ; 2 1
22 1 = p Note that they are rather precise even for low : 10% for the condition (2) can be replaced by the approximate one: = 1 and less. Then 22 1 p
F p 1: If F = 2A, p = 2 B (A > 1, B > 2), then
< 20 and we can safely neglect it; then (2
B) + A 1 0:5 log2
Assume that beside the correct answer of some probability q 1 and M wrong ones with probabilities pm > 0 the set of possible answers contains a subset S of continuously distributed answers of total probability r. Obviously these answers are thrown o by any replication because they have zero probabilities and therefore receiving an answer again is an impossible event. However, wrong answers with positive probabilities can come a few times and be believed. In this case the cost is increased on some penalty Fm.
The results here are completely the same as in the previous section, only the average cost of = 1 case is di erent because estimated value of penalty for an answer from S must be added to the average cost.
Now let us consider the case of countable (M = 1) set of answers with positive probabilities. This assumption may look nice, for example in case when answers are integer numbers. However, such case does not allow equal (or at least comparable) probabilities pm: the series 1 X pm m=1 must converge to some p which is small compared to 1 are given, the average cost p. Provided that pm can still diverge for some or all , depending on behaviour of penalties Fm. It is clear that polynomial (at most) growth of Fm with respect to m is su cient for convergence. To prove that, note that a binomial coe cient grows with polynomial rate: n m 2n; 0 m n; and the sequence pm decreases more quickly that m 1 because it forms a convergent series; therefore su ciently large = makes the terms of the series decrease quickly enough, so the the series converges. Higher only reduce the sum at least (max pm) times, so that the second term in the expression for E decreases. So, for high enough values of the expected cost E grows, almost lineary. Then it has the unique minimal value being the solution to the optimization problem. We have proven that the optimization problem we are studying always has a solution. It is solved in the similar way as the one for the nite set of answers, only the cost function may be equal to in nity for some . Note that the solution can equal 1 in case of low (or no) penalties. This means that no replication is necessary.
It is clear that both countable set of possible answers and continuously distributed set of impossible answers can also be combined.
The work was nancially supported by grants 13-07-00008 and 15-29-07974 of Russian Foundation for Basic Research.