Distributed tree decomposition with privacy

Abstract : Tree Decomposition of Graphical Models is a well known method for mapping a graph into a tree, that is commonly used to speed up solving many problems. However, in a distributed case, one may have to respect the privacy rules (a subset of variables may have to be kept secret in a peer), and the initial network architecture (no link can be dynamically added). In this context, we propose a new distributed method, based on token passing and local elections, that shows performances (in the jointree quality) close to the state of the art Bucket Elimination in a centralized case (i.e. when used without these two restrictions). Until now, the state of the art in a distributed context was using a Depth-First traversal with a clever heuristic. It is outperformed by our method on two families of problems sharing the small-world property.
Type de document :
Communication dans un congrès
CP - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec, Canada. 2012
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00790112
Contributeur : Philippe Dague <>
Soumis le : mardi 19 février 2013 - 14:24:45
Dernière modification le : jeudi 11 janvier 2018 - 06:20:11
Document(s) archivé(s) le : lundi 20 mai 2013 - 04:02:06

Fichier

main-token.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00790112, version 1

Collections

Citation

Vincent Armant, Laurent Simon, Philippe Dague. Distributed tree decomposition with privacy. CP - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec, Canada. 2012. 〈hal-00790112〉

Partager

Métriques

Consultations de la notice

105

Téléchargements de fichiers

525