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 adecentralized 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. |