Synchronous, Asynchronous and Hybrid Algorithms for DisCSP Export

@incollection{brito04, abstract = {There is some debate around the efficiency of synchronous and asynchronous backtracking algorithms for solving DisCSP. The general opinion was that asynchronous algorithms were more efficient than the synchronous ones, because of their higher concurrency. In this work we continue this line of research, and we study the performance of three different procedures, one synchronous, one asynchronous and one hybrid, for solving sparse, medium and dense binary random DisCSP. The synchronous algorithm is SCBJ, a distributed version of the Conflict-Based Backjumping (CBJ) algorithm. The asynchronous algorithm is the standard ABT [2] enhanced with some heuristic. The hybrid algorithm is ABT-Hyb, a novel ABT-like algorithm, where some synchronization is introduced to avoid resending redundant messages. ABT-Hyb behaves like ABT when no backtracking is performed. However, when an agent has to backtrack, it sends a Back message and enters in a waiting state until receiving: a message that allows it to have a value consistent with its agent view, an Info message from the receiver of the last Back message or a Stop message informing that the problem has no solution. During the waiting state, the agent accept any received Info message and rejects as obsolete any received Back message. No matter the synchronous backtracking, ABT-Hyb inherits the good theoretical properties of ABT: it is sound, complete and terminates. This research is supported by the REPLI project TIC-2002-04470-C03-03.}, author = {Brito, Ismel and Meseguer, Pedro}, booktitle = {Principles and Practice of Constraint Programming}, citeulike-article-id = {1585787}, citeulike-linkout-0 = {http://jmvidal.cse.sc.edu/library/brito04.pdf}, doi = {10.1007/b100482}, editor = {Wallace, Mark}, keywords = {bibtex-import, dcsp, multiagent}, posted-at = {2007-08-23 14:42:25}, priority = {2}, title = {Synchronous, Asynchronous and Hybrid Algorithms for {DisCSP}}, url = {10.1007/b100482}, year = {2004} }

TY - CHAP ID - brito04 L3 - citeulike-article-id:1585787 N2 - There is some debate around the efficiency of synchronous and asynchronous backtracking algorithms for solving DisCSP. The general opinion was that asynchronous algorithms were more efficient than the synchronous ones, because of their higher concurrency. In this work we continue this line of research, and we study the performance of three different procedures, one synchronous, one asynchronous and one hybrid, for solving sparse, medium and dense binary random DisCSP. The synchronous algorithm is SCBJ, a distributed version of the Conflict-Based Backjumping (CBJ) algorithm. The asynchronous algorithm is the standard ABT [2] enhanced with some heuristic. The hybrid algorithm is ABT-Hyb, a novel ABT-like algorithm, where some synchronization is introduced to avoid resending redundant messages. ABT-Hyb behaves like ABT when no backtracking is performed. However, when an agent has to backtrack, it sends a Back message and enters in a waiting state until receiving: a message that allows it to have a value consistent with its agent view, an Info message from the receiver of the last Back message or a Stop message informing that the problem has no solution. During the waiting state, the agent accept any received Info message and rejects as obsolete any received Back message. No matter the synchronous backtracking, ABT-Hyb inherits the good theoretical properties of ABT: it is sound, complete and terminates. This research is supported by the REPLI project TIC-2002-04470-C03-03. TI - Synchronous, Asynchronous and Hybrid Algorithms for {DisCSP} T2 - Principles and Practice of Constraint Programming KW - bibtex-import KW - dcsp KW - multiagent AU - Brito, Ismel AU - Meseguer, Pedro A2 - Wallace, Mark PY - 2004/// UR - http://jmvidal.cse.sc.edu/library/brito04.pdf ER -