Log-based Reconciliation Problems

Title: Log-based Reconciliation Problems

Main Research Question: How can we efficiently reconcile divergent replicas of shared objects in a distributed system?

Methodology: The authors propose a log-based approach to reconciliation, where the input is a common initial state and logs of actions performed on each replica. The output is a consistent global schedule that maximizes the number of accepted actions. They develop two programs to solve this problem: a constraint logic program (CLP) and a stochastic local search method with Tabu heuristics (LS).

Results: The authors show that the log-based reconciliation problem is NP-complete. They evaluate the performance of their CLP program on randomly generated benchmarks with varying densities of precedence and dependency constraints between actions. The CLP program finds quasi-optimal solutions up to a thousands of actions and proves optimality up to a hundreds of actions. The LS program, while not proving optimality, computes solutions in an incremental fashion using the initial logs of the application as a starting solution.

Implications: The log-based reconciliation approach offers a general method for handling conflicts in distributed systems, applicable to a wide range of applications. The CLP program provides an efficient way to solve the problem, while the LS program offers an incremental approach that can be useful in practice. The NP-completeness result highlights the complexity of the problem and the need for heuristics and approximation algorithms to tackle larger instances.

Conclusion and Future Work: The authors conclude that the log-based reconciliation approach is a promising solution to the problem of reconciling divergent replicas in distributed systems. They plan to further develop and evaluate their CLP and LS programs, as well as explore other techniques for solving the log-based reconciliation problem.

Link to Article: https://arxiv.org/abs/0109033v1 Authors: arXiv ID: 0109033v1