S. Schulz and W. Blochinger. Parallel SAT-Solving on Peer-to-Peer Desktop Grids. Journal of Grid Computing, accepted.
[ bib | pdf]

»Satciety is a distributed parallel satisfiability (SAT) solver which focuses on tackling the domain-specific problems inherent to one of the most challenging environments for parallel computing - Peer-to-Peer Desktop Grids. Satciety efficiently addresses issues related to resource volatility and heterogeneity, limited node and network capabilities, as well as non-uniform communication costs. This is achieved through a sophisticated distributed task pool execution model, problem size reduction through multi-stage SAT formula preprocessing, context-aware memory management, and adaptive topology-aware distributed dynamic learning. Despite the demanding conditions prevailing in Desktop Grids, Satciety achieves considerable speedups compared to state-of-the-art sequential SAT solvers.«

S. Schulz and W. Blochinger. Cooperate and Compete! A Hybrid Solving Strategy for Task-Parallel SAT Solving on Peer-to-Peer Desktop Grids. In Proc. of the International Conference on High Performance Computing & Simulation (HPCS 2010), Workshop on Parallel Satisfiability Solving, Pages 314-323, Caen, France, June 2010, IEEE Computer Society.
[ bib ]

»The presented work is part of our long-term research goal to develop parallel SAT solving methods for large scale Peer-to-Peer Desktop Grids, which aggregate globally distributed resources. In such a parallel environment, appropriate strategies for dealing with massive parallelism are necessary. In particular, efficiency and at the same time robustness of the parallel methods must be ensured. In this paper we report on a hybrid strategy for parallel SAT Solving, which combines exploratory and competition parallelism in an adaptive way to meet these goals.«

S. Schulz, W. Blochinger, and M. Poths. Orbweb - A Network Substrate for Peer-to-Peer Grid Computing Platforms based on Open Standards. Journal of Grid Computing, 8(1):77-107, Springer, 2010.
[ bib | doi | pdf]

»In this paper, we propose to use the open industrial-strength eXtensible Messaging and Presence Protocol (XMPP) to build a network substrate for Peer-to-Peer Grid computing called Orbweb. We describe how to employ XMPP to tackle domain-specific challenges, including high scalability, support for volatility, NAT/Firewall traversal, and protocol efficiency. Where XMPP fails to meet these requirements, we contribute pertinent extensions. In particular, we boost the scalability of XMPP by taking load of the XMPP servers through dynamically negotiated direct Peer-to-Peer communication channels between XMPP peers. We pave the way for scalable group membership management by substituting the existing XMPP Multi-User Chat protocol for one that does not suffer from limitations imposed by a everyone knows everyone visibility model and allows for selecting a membership model that matches the requirements of a given application. As efficient multicasting is an essential prerequisite for many distributed algorithms and the centralized XMPP multicast is of limited scalability, we adapt the well-known Bimodal Multicast protocol to work in a highly volatile Peer-to-Peer Grid computing environment. Finally, we show how to improve the protocol efficiency of XMPP by leveraging a standardized binary encoding of the XML Information Set for XMPP packet transmission. To substantiate the applicability of our approach and the effectiveness of our extensions, we describe how some important higher-level services used in Peer-to-Peer Grid Computing can be implemented on top of Orbweb and provide a detailed experimental analysis.«

S. Schulz, W. Blochinger and Mathias Poths. A Network Substrate for Peer-to-Peer Grid Computing beyond Embarrassingly Parallel Applications. In Proc. of the International Conference on Communications and Mobile Computing (CMC 2009), Kunming, China, Volume 3, Pages 60-68, IEEE Computer Society.
[ bib | doi | pdf ]

»Embarrassingly parallel Grid applications require no inter-worker interaction. Thus, the underlying communication infrastructure is based on the simple but well understood client/server execution model. This is no longer sufficient if more demanding parallel applications that require true Peer-to-Peer interaction are to be deployed on Grids. In this paper, we propose the industrial-strength eXtensible Messaging and Presence Protocol (XMPP) as a network substrate for these non-trivial Peer-to-Peer Grid Computing applications.«

S. Schulz, W. Blochinger, and H. Hannak. Capability-Aware Information Aggregation in Peer-to-Peer Grids - Methods, Architecture, and Implementation. Journal of Grid Computing, 7(2):135-167, Springer, 2009.
[ bib | doi ]

»Information aggregation is the process of summarizing information across the nodes of a distributed system. We present a hierarchical information aggregation system tailored for Peer-to-Peer Grids which typically exhibit a high degree of volatility and heterogeneity of resources. Aggregation is performed in a scalable yet efficient way by merging data along the edges of a logical self-healing tree with each inner node providing a summary view of the information delivered by the nodes of the corresponding subtree. We describe different tree management methods suitable for high-efficiency and high-scalability scenarios that take host capability and stability diversity into account to attenuate the impact of slow and/or unstable hosts. We propose an architecture covering all three phases of the aggregation process: Data gathering through a highly extensible sensing framework, data aggregation using reusable, fully isolated reduction networks, and application-sensitive data delivery using a broad range of propagation strategies. Our solution combines the advantages of approaches based on Distributed Hash Tables (DHTs) (i.e., load balancing and self-maintenance) and hierarchical approaches (i.e., respecting administrative boundaries and resource limitations). Our approach is integrated into our Peer-to-Peer Grid platform Cohesion. We substantiate its effectiveness through performance measurements and demonstrate its applicability through a graphical monitoring solution leveraging our aggregation system.«

S. Schulz, W. Blochinger, M. Held, and C. Dangelmayr. COHESION - A microkernel based desktop grid platform for irregular task-parallel applications. Future Generation Computer Systems - The International Journal of Grid Computing: Theory, Methods and Applications, 24(5):354-370, 2008.
[ bib | doi ]

»We present Cohesion, a novel approach to Desktop Grid Computing. A major design goal of Cohesion is to enable advanced parallel programming models and application specific frameworks. We focus on methods for irregularly structured task-parallel problems, which require fully dynamic problem decomposition. Cohesion overcomes limitations of classical Desktop Grid platforms by employing Peer-To-Peer principles and a flexible system architecture based on a microkernel approach. Arbitrary modules can be dynamically loaded to replace default functionality, resulting in a platform that can easily adapt to application-specific requirements. We discuss two representative example applications and report on the results of performance experiments that especially consider the high volatility of resources prevailing in a Desktop Grid.«

S. Schulz and W. Blochinger. An integrated approach for managing peer-to-peer desktop grid systems. In Proc. of the Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2007), Rio de Janeiro, Brazil, May 2007.
[ bib | doi ]

»In this paper we propose a comprehensive integrated management architecture for large-scale Desktop Grid systems. By virt ualization of managed entities and automation of repetitive management tasks, we deal with the additional complexity indu ced by the size of these systems. We introduce the concepts of peer-to-peer and disconnected management to cope with netw ork segmentation and node volatility, which are both intrinsic to Desktop Grid systems. By studying real-world use cases, we demonstrate the applicability of our solution.«

W. Blochinger, C. Dangelmayr, and S. Schulz (Authors in alphabetical order). Aspect-oriented parallel discrete optimization on the cohesion desktop grid platform. In Proc. of the Sixth IEEE International Symposium on Cluster Computing and the Grid (CCGrid06), pages 49-56, Singapore, May 2006.
[ bib | doi ]

»Cohesion is an advanced Desktop Grid platform which lays the system-level foundations for parallel programming models and application specific frameworks. It is designed as an extensible layered architecture built around an industrial strength microkernel component. Cohesion provides and integrates advanced functionality required for parallel computing, especially a scalable group model, failure detection and various methods for collective communication. On top of Cohesion we implemented an aspect-oriented framework for parallel discrete optimization. Our work particulary addresses challenges arising from the highly dynamic nature which is inherent in this type of advanced parallel application, like dynamic problem decomposition, load balancing, termination detection and fault tolerance. We report on initial performance measurements indicating the usefulness of our approach.«