Distributed Breakout Revisited

摘要

Distributed breakout algorithm (DBA) is an efficient method for solving distributed constraint satisfaction problems (CSP). Inspired by its potential of being an efficient, low-overhead agent coordination method for problems in distributed sensor networks, we study DBA's properties in this paper. We specifically show that on an acyclic graph of n nodes, DBA can find a solution in O(n~2) synchronized distributed steps. This completeness result reveals DBA's superiority over conventional local search on acyclic graphs and implies its potential as a simple self-stabilization method for tree-structured distributed systems. We also show a worst case of DBA in a cyclic graph where it never terminates. To overcome this problem on cyclic graphs, we propose two stochastic variations to DBA. Our experimental analysis shows that stochastic DBAs are able to avoid DBA's worst-case scenarios and has similar performance as that of DBA.