MURAL - Maynooth University Research Archive Library



    Decentralized constraint satisfaction


    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

    [img]
    Preview
    Download (206kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year