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.
Log-based reconciliation is a new topic for which few algorithms have been developed. The only implementation we know of is the IceCube system reported in @cite_4 . It is worth noting that the objective function of maximizing the number of accepted actions, is different from maximizing the number of satisfied constraints. For that reason, the modeling of log-based reconciliation as a max-CSP problem is inadequate. This is also the main reason why in our second program based on local search, the min-conflict heuristics @cite_10 or the adaptive search method of @cite_0 do not perform well in our modeling, and we use instead a randomized Tabu heuristics.
@cite_0 @cite_10 @cite_4
2121766240 2154193287
We describe a novel approach to log-based reconciliation called IceCube. It is general and is parameterised by application and object semantics. IceCube considers more flexible orderings and is designed to ease the burden of reconciliation on the application programmers. IceCube captures the static and dynamic reconciliation constraints between all pairs of actions, proposes schedules that satisfy the static constraints, and validates them against the dynamic constraints. Preliminary experience indicates that strong static constraints successfully contain the potential combinatorial explosion of the simulation stage. With weaker static constraints, the system still finds good solutions in a reasonable time. IceCube is a system for optimistic replication, supporting collaborative work and mobile computing. It lets users write to shared data with no mutual synchronisation; however replicas diverge and must be reconciled. IceCube is a general-purpose reconciliation engine, parameterised by constraints capturing data semantics and user intents. IceCube combines logs of disconnected actions into near-optimal reconciliation schedules that honour the constraints. IceCube features a simple, high-level, systematic API . It seamlessly integrates diverse applications, sharing various data, and run by concurrent users. This paper focus on the IceCube API and algorithms. Application experience indicates that IceCube simplifies application design, supports a wide variety of application semantics, and seamlessly integrates diverse applications. On a realistic benchmark, IceCube runs at reasonable speeds and scales to large input sets. Facility dispersion problem deals with the location of facilities on a network so as to maximize some function of the distances between facilities. We consider the problem under two different optimality criteria, namely maximizing the minimum distance (MAX-MIN) between any pair of facilities and maximizing the average distance (MAX-AVG) between any pair of facilities. Under either criterion, the problem is known to be NP-hard, even when the distances satisfy the triangle inequality. We consider the question of obtaining near-optimal solutions. For the MAX-MIN criterion, we show that if the distances do not satisfy the triangle inequality, there is no polynomial time relative approximation algorithm unless P=NP. When the distances do satisfy the triangle inequality, we present an efficient heuristic which provides a performance guarantee of 2, thus improving the performance guarantee of 3 proven in [Wh91]. We also prove that obtaining a performance guarantee of less than 2 is NP-hard. For the MAX-AVG criterion, we present a heuristic which provides a performance guarantee of 4, provided that the distances satisfy the triangle inequality. For the 1-dimensional dispersion problem, we provide polynomial time algorithms for obtaining optimal solutions under both MAX-MIN and MAX-AVG criteria. Using the latter algorithm, we obtain a heuristic which provides a performance guarantee of 4( ( 2 - 1 ))  1.657 for the 2-dimensional dispersion problem under the MAX-AVG criterion.