@Article{hirayama05a,
  author =	 {Katsutoshi Hirayama and Makoto Yokoo},
  title =	 {The distributed breakout algorithms},
  journal =	 {Artificial Intelligence},
  year =	 2005,
  volume =	 161,
  number =	 {1--2},
  pages =	 {89--115},
  doi =		 {10.1016/j.artint.2004.08.004},
  abstract =	 {We present a new series of distributed constraint
                  satisfaction algorithms, the distributed breakout
                  algorithms, which is inspired by local search
                  algorithms for solving the constraint satisfaction
                  problem (CSP). The basic idea of these algorithms is
                  for agents to repeatedly improve their tentative and
                  flawed sets of assignments for variables
                  simultaneously while communicating such tentative
                  sets with each other until finding a solution to an
                  instance of the distributed constraint satisfaction
                  problem (DisCSP). We introduce four implementations
                  of the distributed breakout algorithms: SINGLE-DB,
                  MULTI-DB, MULTI-DB+, and MULTI-DB++. SINGLE-DB is a
                  distributed breakout algorithm for solving the
                  DisCSP, where each agent has a single local variable
                  and its related constraints. MULTI-DB, on the other
                  hand, is another distributed breakout algorithm for
                  solving the distributed SAT (DisSAT) problem, where
                  each agent has multiple local variables and their
                  related clauses. MULTI-DB+ and MULTI-DB++ are
                  stochastic variations of MULTI-DB. In MULTI-DB+, we
                  introduce a technique called random break into
                  MULTI-DB; in MULTI-DB++, we introduce a technique
                  called random walk into MULTI-DB+. We conducted
                  experiments to compare these algorithms with the
                  asynchronous type of distributed constraint
                  satisfaction algorithm. Through these experiments,
                  we found that SINGLE-DB, MULTI-DB, and MULTI-DB+
                  scale up better than the asynchronous type of
                  distributed constraint satisfaction algorithms, but
                  they sometimes show very poor performance. On the
                  other hand, we also found that MULTI-DB++, which
                  uses random walk, provides a clear performance
                  improvement.},
  keywords =     {multiagent dcsp},
  url = 	 {http://jmvidal.cse.sc.edu/library/hirayama05a.pdf},
  cluster = 	 {16433191502258072101}
}