Solving Distributed CSPs Probabilistically

Issue title: On the Italian Conference on Computational Logic: CILC 2009

Article type: Research Article

Authors: Bistarelli, Stefano^; | Gosti, Giorgio^;

Affiliations: Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Italy. bista@dmi.unipg.it | Istituto di Informatica e telematica (IIT-CNR) Pisa, Italy. stefano.bistarelli@iit.cnr.it | Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Italy | Institute for Mathematical Behavioral Sciences, University Of California, Irvine, USA. ggosti@uci.edu

Note: [] Address for correspondence: IMBS, Social Science Plaza A, School of Social Sciences, Irvine, CA 92697-5100, USA

Abstract: Constraint solving problems (CSPs) are the formalization of a large range of problems that emerge from computer science. The solving methodology described here is based on the naming game. The two main features that distinguish this methodology from most distributed constraint solving problem (DCSPs) methods are: the system can react to small instance changes, and it does not require pre-agreed agent/variable ordering. The naming game was introduced to represent N agents that have to bootstrap an agreement on a name to give to an object. The agents do not have a hierarchy, and use a minimal protocol. Still they converge to a consistent state by using a distributed strategy. For this reason, the naming game can be used to untangle DCSPs. It was shown that a distributed system of uniform finite state machines does not solve the ring ordering problem in all the algorithm executions. Our algorithm is a distributed uniform system of agents able to perform random decisions when presented with equivalent alternatives. We show that this algorithm solves the ring ordering problem with a probability one.

DOI: 10.3233/FI-2010-358

Journal: Fundamenta Informaticae, vol. 105, no. 1-2, pp. 57-78, 2010