Mostrar el registro sencillo del ítem

A Distributed Algorithm for Resource Clustering in Large Scale Platforms

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorDUCHON, Philippe
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorLARCHEVÊQUE, Hubert
dc.date.accessioned2024-04-15T09:51:56Z
dc.date.available2024-04-15T09:51:56Z
dc.date.issued2008
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198477
dc.description.abstractEnWe consider the resource clustering problem in large scale distributed platforms, such as BOINC, WCG or Folding@home. In this context, applications mostly consist in a huge set of independent tasks, with the additional constraint that each task should be executed on a single computing resource. We aim at removing this last constraint, by allowing a task to be executed on a (small) set of resources. Indeed, for problems involving large data sets, very few resources may be able to store the data associated to a task, and therefore may be able to participate in the computations. Our goal is to propose a distributed algorithm for a large set of resources that enables to build clusters, each of which will be responsible for processing a task and storing associated data. From an algorithmic point of view, this corresponds to a bin covering problem with an additional distance constraint. Each resource is associated to a weight (its capacity) and a position in a metric space (its location, based on network coordinates such as those obtained with Vivaldi), and the aim is to build a maximal number of clusters, such that the aggregated power of each cluster (the sum of the weights of its resources) is large enough and such that the distance between two resources belonging to the same cluster is kept small (in order to minimize intra-cluster communication latencies). In this paper, we describe a generic 2-phases algorithm, based on resource augmentation and whose approximation ratio is 1/3. We also propose a distributed version of this algorithm when the metric space is $\mathbb{Q}^D$ (for a small value of $D$) and the $L_{\infty}$ norm is used to define distances. This algorithm takes $O((4^D) \log^2n)$ rounds and $O((4^D)n\log n)$ messages both in expectation and with high probability,where $n$ is the total number of hosts.
dc.language.isoen
dc.title.enA Distributed Algorithm for Resource Clustering in Large Scale Platforms
dc.typeRapport
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionINRIA
bordeaux.type.reportrr
hal.identifierinria-00369417
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00369417v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2008&rft.au=BEAUMONT,%20Olivier&BONICHON,%20Nicolas&DUCHON,%20Philippe&EYRAUD-DUBOIS,%20Lionel&LARCHEV%C3%8AQUE,%20Hubert&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem