How to eliminate some redundancy in the 4th result
3 Aug 2005 7:13:11 UTC
Topic 189654
(moderation:
There has always been discussion, sometimes heated, about the perceived "waste" of sending redundant work units in excess of the actual required quorum. Much of the commentary seems to severly overstate the "problem" that this policy entails. My personal opinion is that the current riches of computing resources and willing volunteers hardly requires any thought at all to be devoted to this issue.
However, looking ahead, I can see the day coming where there are many worthwhile projects competing for those computing resources so that there is benefit in gradually improving efficiency of usage of those resources. It's always good for a project to get the same work done using fewer resources.
I have not done any hard research on this but observation of my own results suggests that many are validated within quite a short period of the original issue time - perhaps a day or two at the most. I wouldn't be at all surprised to see 50% or more results validated within 2 days of issue. Perhaps this might be different for other projects with different deadlines. It would certainly be different for older, slower computers and/or situations where a significant local cache is stored (user policy).
However, let's limit the discussion to those projects with a 7 to 14 day deadline. Let's also assume that there are no significant "frontrunners" where the first copy can be dished out significantly ahead of the rest. When requests for work are made, there is serverside software that hands the work out, X copies at a time where X is at least one more than the required quorum. Presumably that software could easily be modified to hand out initially just the required quorum and then wait a predetermined interval before sending out the extra copy(ies). I would envisage that interval being of the order of one to two days. If a valid quorum was formed within that interval, the extra copy(ies) would be cancelled. If not they would be sent immediately the interval had expired.
I imagine that this wouldn't be too hard to implement as there is existing code that sends out extra copies when deadlines expire without a quorum being formed. It would seem to be just an adaption of that type of code. The benefit would seem to be the elimination of a significant proportion of the redundant work units. The downside would be increased load on the server to keep track of it all.
I would imagine that this has all been thought of before but I just thought I'd bring it up anyway. It would be interesting to know if there is a good reason why something like this is not practicable. Any and all comments are most welcome.
Cheers,
Gary.
How to eliminate some redundancy in the 4th result
)
I imagine there are proportionally more hosts with higher turnaround times than hosts with lower ones (although I really don't know). So presumably a relatively large delay for the fourth host allocation would be required to effect significantly less hosts being allocated. That is, I think there would typically be 'frontrunners' because of this.
The savings also won't work where one of the required hosts has an infrequent connection time. I don't know what proportion of hosts have frequent connection times, but where users are running multiple projects this would be typical.
One would have to take into account whether the spread of hosts favours a small delay and whether a significant proportion of hosts have frequent connection times. I suppose in Einstein@Home's case it would reduce the 25% wastage to about 15-20%, although I am not qualified to make such a judgement.
I know you mentioned frontrunners and large caches, sorry if this reply is not what you wanted. I really have no clue what it would take to implement. I really should read what people say before replying. It would help some...
The way to save the crunching
)
The way to save the crunching of the extra WU is to only send the initial 3 and wait until the deadline passes to send to 4th.
It may also be possible to look at the history of the clients. Take the number of correct returns in the last 100 WUs (if there is not a history of 100 count the others as failures) for the first three clients to connect. Multiply these together, and if it is less than some threshold, send the insurance WU. This means that a new client will always generate the insurance WU, but if the first three computers have had 100 successes in a row each, the insurance WU will not be needed (pretty good bet).
If BOINC is anything like S@H classic fully half of the clients that connected never returned the first WU. 80% never made it to 100 WUs, and the rest were pretty reliable (with a very occasional random system crash).
BOINC WIKI