Solving Distributed CSPs Probabilistically

Constraint solving problems (CSPs) are the formalization of a large range of problems that emerge fromcomputer 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.