Ken Duffy | Hamilton Institute, National University of Ireland Maynooth
Ken Duffy
Hamilton Institute
NUI Maynooth

Decentralized Constraint Satisfaction

In the submitted article Decentralized Constraint Satisfaction, written with Charles Bordenave and Douglas J. Leith,
we present a decentralized solver that will provably find a solution to a Constraint Satisfaction Problem, should one exist.
To give some intuition as to the manner in which a solution is found, here are two Java applets (first written by interns
Tony Poole and John Roche) that illustrate the algorithms evolution in real-time on distinct classes of problems.

Decentralized Graph Colouring

In vertex graph colouring, each vertex is attempting to find a colour that is distinct from the colours of all its neighbours.
A link between vertices is red if that constraint is dissatisfied (i.e. if the two linked vertices are the same colour) and green
otherwise. For comparison, two centralized algorithms, one inspired by Stochastic Local Search and one by
Davis-Putnam-Logemann-Loveland are presented. The star toplogy, which is hard to colour in a decentralized fashion, was
added in response to a suggestion by KTH's Alexandre Proutiere.

Suggested setting: 250 Variables, CFL, 4 Colours, High Complexity, Generate and Start.

Decentralized Concensus Finding

Finding global concensus is an example of a problem that is easy for a centralized algorithm, but challenging for a
decentralized one that only has local information. Here the objective is for all vertices to select the same colour so a link
between verticies is red if their colours are distinct and green if they are the same. This illustration was inspired by a
conversation with MIT's Muriel Medard.

Suggested setting: 250 Variables, Low Complexity, Generate and Start.