@InCollection{brito04,
  author =	 {Ismel Brito and Pedro Meseguer},
  title =	 {Synchronous, Asynchronous and Hybrid Algorithms for {DisCSP}},
  booktitle =	 {Principles and Practice of Constraint Programming},
  year =	 {2004},
  editor = 	 {Mark Wallace},
  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.},
  keywords =     {multiagent dcsp},
  isbn = 	 {3-540-23241-9},
  doi = 	 {10.1007/b100482},
  url = 	 {http://jmvidal.cse.sc.edu/library/brito04.pdf},
  cluster = 	 {15818556906404522057}
}