Yoyo@home A publication on Harmonious Trees and Odd Weird Search

[Newshound]

It has been a long time, we know, that there was no news whatsoever the results of Harmonious Trees,
or Odd Weird Search. All we knew was that we found nothing, the conjectures remained safe, and even taking
on more credence. It sounds a bit anti-climatic.

But no! In this interval, we have been busy working on something. It is a research article, to be precise,
that describes what we did to make both projects possible, what we observed, and what we can do to make it better
(if there is a similar problem to be made into a volunteer computing project).
And finally, after a lot of writing and editing in between great periods of procrastination (yes, I did a PhD in math
in between, and yoyo of course needs to maintain the project alongside his work), today it is finally published!

Titled Parallel Tree Search in Volunteer Computing: a Case Study, the article can be found here:
https://link.springer.com/article/10.10 ... 017-9411-5

It is open access, meaning that everyone can download it and have a look freely.
Thanks to TU Graz (I am a postdoc there), FWF (the Austria founding agency) and the library of TU Graz for having an
open access arrangement with Springer. Otherwise, the authors generally have to pay thousands of dollars for the open
access option. So, enjoy if you are interested!

Here is an abstract of the article:

While volunteer computing, as a restricted model of parallel computing, has proved itself to be a successful paradigm
of scientific computing with excellent benefit on cost efficiency and public outreach, many problems it solves are
intrinsically highly parallel. However, many efficient algorithms, including backtracking search, take the form of a
tree search on an extremely uneven tree that cannot be easily parallelized efficiently in the volunteer computing
paradigm. We explore in this article how to perform such searches efficiently on volunteer computing projects.
We propose a parallel tree search scheme, and we describe two examples of its real-world implementation, Harmonious Tree
and Odd Weird Search, both carried out at the volunteer computing project yoyo@home. To confirm the observed efficiency
of our scheme, we perform a mathematical analysis, which proves that, under reasonable assumption that agrees with
experimental observation, our scheme is only a constant multiplicative factor away from perfect parallelism. Details
on improving the overall performance are also discussed.

SOURCE http://www.rechenkraft.net/yoyo//all_news.php#287