Duffy, Ken R. and Borgenave, C. and Leith, Douglas J. (2013) Decentralized constraint satisfaction. IEEE/ACM Transactions on Networking, 21 (4). pp. 1298-1308. ISSN 1063-6692

Preview

Download (206kB) | Preview

Abstract

Constraint satisfaction problems (CSPs) lie at the heart of many modern industrial and commercial tasks. An important new collection of CSPs has recently been emerging that differ from classical problems in that they impose constraints on the class of algorithms that can be used to solve them. In computer network applications, these constraints arise as the variables within the CSP are located at physically distinct devices that cannot communicate. At each instant, every variable only knows if all its constraints are met or at least one is not. Consequently, the CSP’s solution must be found using a decentralized approach. Existing algorithms for solving CSPs are either centralized or distributed, both of which fundamentally violate these algorithmic constraints. In this article we present the first algorithm for solving CSPs that satisfies these new constraints. It is fully decentralized, making no use of a centralized controller or message-passing between variables. We prove that this algorithm converges with probability one to a satisfying assignment whenever one exists. Surprisingly, we experimentally demonstrate that the time the algorithm takes to find a satisfying assignment is competitive with bothWalkSat and Survey Propagation, two popular and efficient CSP solvers. That is, despite its decentralized nature the algorithm is remarkably fast. This raises new questions about the relationship between information sharing and algorithm performance.

Item Type:	Article
Additional Information:	This is the preprint version of the published article, which is available at DOI: 10.1109/TNET.2012.2222923
Keywords:	Channel allocation; EDMA; learning automata; network coding; stochastic processes; wireless networks;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	6218
Identification Number:	https://doi.org/10.1109/TNET.2012.2222923
Depositing User:	Dr Ken Duffy
Date Deposited:	29 Jun 2015 14:40
Journal or Publication Title:	IEEE/ACM Transactions on Networking
Publisher:	IEEE
Refereed:	Yes
Funders:	Science Foundation Ireland (SFI)
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads