Francois Fages
INRIA Rocquencourt. 
Projet Contraintes.

TITRE:
Une approche des problèmes de reconciliation à base de traces
en programmation par contraintes.

RESUME:
Les applications nomades créent des copies d'objets partagés
qui évoluent de façon indépendante quand elles sont déconnectées.
Au moment de la reconnexion le système doit reconcilier les
copies divergentes. La reconciliation à base de traces est un problème
d'optimisation dans lequel l'entrée est un état initial commun
et des traces d'actions exécutées sur chaque copie, la sortie est un
ordonnancement global cohérent qui maximise le nombre d'actions
acceptées. Le reconciliateur fusionne les actions suivant l'ordonnancement
calculé, et rejoue les actions fusionnées à partir de l'état initial,
ce qui produit un état réconcilié commun.

Dans cet exposé je montre que la reconciliation à base de traces est 
un problème NP-difficile et présente un programme logique avec contraintes
qui utilise des contraintes sur les nombres entiers, pour exprimer
les précédences entre actions, et des contraintes booléennes pour
exprimer les dépendances entre actions. On montre l'existence d'un pic de 
complexité autour des densités 7 pour les contraintes de précédence et 0 
pour les contraintes de dépendance entre actions. 
Sur des exemples plus réalistes de densité 1.5 les évaluations montrent 
que le programme trouve des solutions proches de l'optimum pour un millier
d'actions et prouve l'optimalité jusqu'à quelques centaines d'actions.