Although today’s largest Desktop Grid harvests idle cycles from only 0.46‰ of the Personal Computers (PC) deployed world-wide, it is way ahead of the currently fastest supercomputer with respect to raw computing performance. If it were possible to attract roughly 7% of the world’s PC owners to donate their resources, the resulting virtual supercomputer would right now punch through the exascale barrier expected to be broken by supercomputers not until around the year 2020.

However, the full potential of Desktop Grid Computing has not yet been unleashed in another respect: application support. Due to their centralized interaction model Desktop Grids are currently limited to embarrassingly parallel applications. By complementing the foundations of Desktop Grid Computing systems with Peer-to-Peer concepts and methods, their scope can be extended to non-trivial applications from the field of High-Performance Computing, like parallel search problems – including discrete optimization, constraint satisfaction, and satisfiability solving –, Raytracing, or N-Body simulations. These applications are all instances of a special class of parallel applications called Irregularly Structured Problems (ISP). Their computation and interaction patterns are input-dependent, unstructured, and evolving.

The incorporation of Peer-to-Peer methods has impact on many aspects of Desktop Grid Computing systems: Their architecture has to be retrofitted to support decentralized operation by multiple authorities in a secure and safe environment. The plethora of algorithmic alternatives available beyond Client/Server interaction requires the system to be designed for extensibility from the ground up. Solving task-parallel ISPs requires much more sophisticated platform support in the form of a distributed task pool that is able to perform dynamic decomposition, load balancing, and termination detection in a decentralized and fault-tolerant way. To support this decentralized execution model the underlying network substrate must provide efficient Peer-to-Peer unicast and multicast primitives and the ability to rapidly report available resources and their vanishing, both without seriously impairing scalability.

Cohesion, the next generation Desktop Grid Computing platform described in this thesis, is an amalgamation of novel approaches designed to tackle these challenges. It’s capacity to efficiently execute task-parallel ISPs in volatile and heterogeneous Desktop Grids is demonstrated by means of Satciety, a state-of-the-art distributed SAT solver build on top of Cohesion.