Peer-to-peer desktop grid

From Colettapedia
Jump to: navigation, search

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

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