Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks
BENOIT, Anne
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
LARCHEVÊQUE, Hubert
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
RENAUD-GOUD, Paul
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
BENOIT, Anne
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
LARCHEVÊQUE, Hubert
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
RENAUD-GOUD, Paul
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
< Réduire
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Langue
en
Rapport
Ce document a été publié dans
2011-09p. 26
Résumé en anglais
In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to ...Lire la suite >
In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.< Réduire
Mots clés en anglais
Replica placement
distance constraints
optimal algorithms
approximation algorithms
tree networks
binary tree
single vs multiple policy.
single vs multiple policy
Origine
Importé de halUnités de recherche