Reducing Redundant Messages in the Asynchronous Backtracking Algorithm
Hong Jiang and Jos´e M. Vidal

Abstract

We show how the Asynchronous Backtracking Algorithm, a well known distributed constraint satisfaction algorithm, produces unnecessary messages. Our new optimized algorithm reduces the number of messages by implementing message management mechanism. Tests show our algorithm significantly reduces the total number of messages sent and drastically reduces the number of cycles used when solving instances of the graph coloring problem.