  Nomadic applications create replicas of shared objects that evolve
independently while they are disconnected. When reconnecting, the system has to
reconcile the divergent replicas. In the log-based approach to reconciliation,
such as in the IceCube system, the input is a common initial state and logs of
actions that were performed on each replica. The output is a consistent global
schedule that maximises the number of accepted actions. The reconciler merges
the logs according to the schedule, and replays the operations in the merged
log against the initial state, yielding to a reconciled common final state.
  In this paper, we show the NP-completeness of the log-based reconciliation
problem and present two programs for solving it. Firstly, a constraint logic
program (CLP) that uses integer constraints for expressing precedence
constraints, boolean constraints for expressing dependencies between actions,
and some heuristics for guiding the search. Secondly, a stochastic local search
method with Tabu heuristic (LS), that computes solutions in an incremental
fashion but does not prove optimality. One difficulty in the LS modeling lies
in the handling of both boolean variables and integer variables, and in the
handling of the objective function which differs from a max-CSP problem.
Preliminary evaluation results indicate better performance for the CLP program
which, on somewhat realistic benchmarks, finds nearly optimal solutions up to a
thousands of actions and proves optimality up to a hundreds of actions.
