Peer-to-peer desktop grid
Questions
- Which classes of applications can benefit from P2P grid computing? ANS: Irregularly Structured Problems:
- ISPS - parallel applications, whose computation and interaction patterns are input-dependent, unstructured and evolving during the computation.
Desktop grid description
architecture
- group membership management - provides ability to organize the set of participating nodes into dynamic functional subsets and to make nodes within a group visible to each other accordig to an application-specific topology.
- failure detection service - determine whether a node left the group intentionally or as a consequence of failure.
- membership views - expose current set of know non-faulty peers to application
- highly configurable application container
requirements
- distributed grid must by definition be concurrent
benefits
- highly redundant - fault tolerant
- high scalability
- ad-hoc self organization
- discovery
- grouping of peers
- NAT/firewall traversal
- resource sharing
issues
- volatility - resources join and leave in an unpredictable manner
- non-dedication - nodes of grid used primarily for other purpose
- heterogeneity - different platforms
- machine owner constraints
- non-uniform communication costs - firewalls
- down side of client-server: parallel programming models requiring complex interaction patterns among nodes cannot be realized efficiently
Concepts
Exploratory decomposition
- structures a parallel program execution into a set of interacting tasks.
- Each task consists of a sequence of operations that can include the creation on new tasks which may later be transferred to other nodes for load balancing
- Task pool - shared data structure to store and manage tasks created during execution. All computes nodes and extract tasks from the queue, and enqueue new tasks.
- centralized - bottleneck. master node maintains global task queue from which idle nodes can fetch tasks
- P2P - a pool is located on every compute node. Control logic of load balancing, fault tolerance, and termination detection is more challenging.
Load balancing
- Random stealing ("pull-based load balancing") & random pushing - selection of strategy governed by problem to be solved, and environment computation is to be executed in
- Task size, inter-task dependency with structure that changes dynamically, arbitrary comunication patterns, dynamically changing set of compute nodes potentially experiencing concurrent loads
- When to trigger task decomposition???
- on-demand decomposition
Technologies
Desktop Grid Implementations
Client/server model
- boinc
- Entropia
P2P model
- JNGI - built on top of JXTA - https://jxta-jngi.dev.java.net/
- P3 - also built on top of JXTA
- Cohesion
Hybrid
- ORBWEB
- part of network functionality is delegated to a small number of distinguished peers called superpeers.
- delegates group management and failure detection to superpeers, thus allowing for rapid membership view updates
- builds on and extends the open eXtensible Messaging and Presence Protocol (XMPP)
unsorted
- XMPP - Extensible Messaging and Presence Protocol (XMPP) is an open-standard communications protocol for message-oriented middleware based on XML
- Globus - mainstream grid computing middleware
Paper Reviews
SAT solving paper using Cohesion, Schulz et al., 2010
- Resource volatility, heterogeneity, limited node and network capabilities, non-uniform communication costs
- "distributed task pool execution model"
- problem size reduciton
- multi-stage SAT
- "adaptive topology-aware distributed dynamic learning"
Distributed Computing Systems: P2P versus Grid Alternatives
- A. Cabani et al 2007
- How to identify the right distributed computing alternative, P2P vs. grid