Distributed Constraint Satisfaction applied to Log-based Reconciliation
Yek Loong Chong  and Youssef Hamadi

Abstract

 This paper presents four distributed algorithms for log-based reconciliation. Our methods remove the classical drawbacks of central- ized systems like single point of failure, performance bottleneck and loss of autonomy. They are tolerant to failures and allow operations to per- form multi-object updates without forcing full replication. The prob- lem is formalized using the Distributed Constraint Satisfaction paradigm (DisCSP). In the worst case, the message passing complexity of our meth- ods range from O(p 2 ) to O(2 p ) in a system of p nodes. Experimental results con rm our theoretical analysis and allow us to establish quality and eÆciency trade-o  for each method.