Asynchronous Backtracking with temporary and fixed links: A New Hybrid Member in the ABT Family

Abstract

Starting from the algorithm of asynchronous backtracking (ABT), a unifying framework for some of the asynchronous techniques has recently been suggested (called ABT kernel). Within this unifying framework, several techniques have been derived, known as the ABT family. They differ in the way they store nogoods, but they all use additional communication links between unconnected agents to detect obsolete information. A first way to remove obsolete information is to add new communication links to allow a nogood owner to determine whether this nogood is obsolete or not. These added links were proposed in the original ABT algorithm. The second solution consists in temporary keeping the links. A new link remains until a fixed number of messages have been exchanged through it. After that, it is removed. In this article is proposed a solution for the elimination of outdated informations between agents, by adding new links for the purpose of informing the agents, some links becoming permanent, others temporary. It consists in combining the permanent links with the temporary ones. The solution is based on determining the number of messages necessary for keeping the temporary links, number determined dynamically during the runtime. Based on these informations some links become permanent, others are kept temporary, until that number of messages is exchanged between the agents connected by temporary links. A new hybrid technique can be obtained from ABT kernel by applying this method, the experiments show a better efficiency in comparison with the asynchronous backtracking.