Asynchronous Backtracking for Asymmetric DisCSPs
Roie Zivan and Amnon Meisels

Abstract

Distributed constraint satisfaction problems (DisCSPs) with asym-metric constraints reflect the fact that agents may wish to retain their constraints private. The set of pairs of values of every binary constraint is split between the two constrained agents. An asynchronous backtracking algorithm for asymmetric DisCSPs is presented. The new algorithm is based on asynchronous backtracking (ABT), but, propa-gates assignments both to lower priority agents and to higher priority agents. The proposed ABT ASC algorithm is proven sound and complete. The ABT ASC algorithm is evaluated experimentally on randomly generated asymmetric DisCSPs. Its performance is compared to that of the privacy keeping version of ABT, proposed by Brito and Meseguer, which splits the search into two phases. The ABT ASC algorithm improves the run-time of the 2-phase ABT by a large factor with no additional load on the communication network.