CLP versus LS on Log-based Reconciliation Problems

Details CLP versus LS on Log-based Reconciliation Problems CLP versus LS on Log-based Reconciliation Problems

2001-09-18

arxiv.org/abs/cs/0109033v1

Computer Science

Programming Languages

Article presented at the 6th ERCIM workshop of the Constraint Group, Prague, Czech Republic, June 2001

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

CLP versus LS on Log-based Reconciliation Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with CLP versus LS on Log-based Reconciliation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CLP versus LS on Log-based Reconciliation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424910